Converse of Fermat's Little Theorem.
If $a^n\equiv a \pmod n$ for all integers $a$, does this imply that $n$ is prime?
I believe this is the converse of Fermat's little theorem.
$\endgroup$ 42 Answers
$\begingroup$No, the converse of Fermat's Little Theorem is not true. For a particular example, $561 = 3 \cdot 11 \cdot 17$ is clearly composite, but $$ a^{561} \equiv a \pmod{561}$$ for all integers $a$. This is known as a Carmichael Number, and there are infinitely many Carmichael Numbers.
$\endgroup$ $\begingroup$Here is one more example:
We see that $341 = 11 \cdot31$ and $2^{340} = 1\mod341$
To show this we see that by routine calcultions the following relations hold $$2^{11} = 2\mod31 $$$$ 2^{31} = 2 \mod 11$$
Now by using Fermat's little theorem $$ ({2^{11}})^{31} = 2^{11} \mod 31 $$ but $2^{11} = 2 \mod 31$ so I leave you to fill the details of showing $2^{341} = 2 \mod 341$.
$\endgroup$
