# Prime Numbers and Primitive Roots

Let $p_1$, $p_2$, $p_3$ different prime numbers. Let $N = p_1p_2p_3$. Given $(p_1-1)|(N-1), (p_2-1)|(N-1)$ and $(p_3-1)|(N-1)$, prove that for every number $a \in \Bbb N$ such that $\gcd(a,N) = 1$ , $a^N \equiv a \mod N$. I'd be grateful if anyone could point me to the solution, thanks in advance.

• This is a simple application of Fermat's Little Theorem and the Chinese Remainder Theorem. – fretty Aug 14 '13 at 10:33
• For one of the directions of the proof, we need the existence of a primitive root, that is a number $b$ with $ord_b(p)=p-1$. For every prime $p$, such a $b$ exists. For the required direction, we do not need this. – Peter Oct 14 '15 at 19:50

Numbers with this property are called Carmichael numbers (the definition is analogue for more than $3$ prime factors). I will give the proof for every number of prime factors.
A Carmichael number must be odd and squarefree and must have at least $3$ prime factors. $N=\prod_{j=1}^k p_j$ with $2<p_1<p_2<...<p_k$ is a Carmichael number, that is $a^{N-1}\equiv 1\ (\ mod\ N)$ holds for every $a$ coprime to $N$, if and only if $p_j-1|N-1$ for $j=1,...,k$.
Suppose : $p_j-1$ divides $N-1$ for $j=1,...,k$. Then, for every number $a$ coprime to $N$ we have $a^{p_j-1}\equiv 1\ (\ mod\ p_j\ )$ for $j=1,...,k$. Since $p_j-1|N-1$, we get $a^{N-1}\equiv 1\ (\ mod\ p_j)$ , $j=1,...,k$ and therefore $a^{N-1}\equiv 1\ (\ mod\ N\ )$
The other direction is a bit more tricky. Suppose, $a^{N-1}\equiv 1\ (\ mod\ n\ )$ for all $a$ coprime to $N$. Let $a$ be a number with $ord_a(p_j)=p_j-1$ , $j\in [1,...,k]$.Choose a number $b$ with $b\equiv a\ (\ mod\ p_j)$ and $b\equiv 1\ mod(\ p_i\ )$ for $i\ne j$. Then, $b$ is coprime to $N$ and $ord_b(p_j)=p_j-1$. With $b^{N-1}\equiv 1\ (\ mod\ N\ )$ we get $p_j-1|N-1$.