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

• en.wikipedia.org/wiki/Carmichael_number Feb 9, 2016 at 3:37
• Try $n = 561$ or $n = 512461$. These are examples of Carmichael numbers (see the previous comment). The phenomenon is interesting enough to have attracted the attention of many well-known mathematicians. Feb 9, 2016 at 3:40
• and see en.wikipedia.org/wiki/Fermat_primality_test#Flaw (but that test is still very useful, for example for RSA keys generation) Feb 9, 2016 at 4:41
• No, carmichael numbers are counterexamples, e.g. see here and here. But there are some valid comverses e.g that by Lucas Dec 20, 2019 at 21:13

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