1. ## Carmichael number

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

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

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

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

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