1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is a simple application of Fermat's Little Theorem and the Chinese Remainder Theorem. $\endgroup$ – fretty Aug 14 '13 at 10:33
  • $\begingroup$ 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. $\endgroup$ – Peter Oct 14 '15 at 19:50
1
$\begingroup$

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$.

One direction is easy :

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.