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.
Elementary Number Theory – Converse of Fermat’s Little Theorem
elementary-number-theory
elementary-number-theory
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.
Best Answer
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.