1. ## Carmichael number

Show that if $\displaystyle n = p_{1} \cdots p_{k}$, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j$ and for every $\displaystyle i, p_{i}-1 \mid n-1$, then $\displaystyle n$ is a Carmichael number.

2. Originally Posted by chiph588@
Show that if $\displaystyle n = p_{1} \cdots p_{k}$, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j$ and for every $\displaystyle i, p_{i}-1 \mid n-1$, then $\displaystyle n$ is a Carmichael number.
We will show that if $\displaystyle a>0$ and $\displaystyle \gcd(a,n)=1$ then $\displaystyle a^{n-1}\equiv 1(\bmod n)$. Define the group $\displaystyle G = \mathbb{Z}_n^{\times} \simeq \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times}$. Now $\displaystyle x\in \mathbb{Z}_{p_1}^{\times} \times ... \times \mathbb{Z}_{p_k}^{\times}$ then $\displaystyle x^n$ is the identity because $\displaystyle \mathbb{Z}_{p_i}^{\times} \simeq \mathbb{Z}_{p_i-1}$ and $\displaystyle (p_i - 1)|(n-1)$. Therefore, if $\displaystyle b\in G$ then we see that $\displaystyle b^n$ is the identity. Thus, $\displaystyle a^n \equiv 1(\bmod n)$.

3. Is there a way to do it without fields?

4. Originally Posted by chiph588@
Show that if $\displaystyle n = p_{1} \cdots p_{k}$, where $\displaystyle p_{i} \neq p_{j} \; \forall \; i \neq j$ and for every $\displaystyle i, p_{i}-1 \mid n-1$, then $\displaystyle n$ is a Carmichael number.
suppose $\displaystyle \gcd(a,n)=1.$ then $\displaystyle \gcd(a,p_i)=1,$ for all $\displaystyle i.$ let $\displaystyle n-1=k_i(p_i-1), \ i=1, \cdots , k.$ by Fermat's little theorem: $\displaystyle a^{n-1}=(a^{p_i -1})^{k_i} \equiv 1 \mod p_i,$ for all $\displaystyle i.$ thus $\displaystyle \forall \ i: \ p_i \mid a^{n-1} - 1.$

so, since $\displaystyle p_1, \cdots , p_k$ are distinct, we'll have $\displaystyle n=p_1p_2 \cdots p_k \mid a^{n-1} - 1. \ \Box$