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.
$\begingroup$
$\endgroup$
4
asked Feb 9, 2016 at 3:32
-
4$\begingroup$ en.wikipedia.org/wiki/Carmichael_number $\endgroup$– Will JagyCommented Feb 9, 2016 at 3:37
-
$\begingroup$ 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. $\endgroup$– Hans EnglerCommented Feb 9, 2016 at 3:40
-
1$\begingroup$ and see en.wikipedia.org/wiki/Fermat_primality_test#Flaw (but that test is still very useful, for example for RSA keys generation) $\endgroup$– reunsCommented Feb 9, 2016 at 4:41
-
1$\begingroup$ No, carmichael numbers are counterexamples, e.g. see here and here. But there are some valid comverses e.g that by Lucas $\endgroup$– Bill DubuqueCommented Dec 20, 2019 at 21:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Oct 25, 2016 at 19:31
$\begingroup$
$\endgroup$
1
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$.
answered May 6, 2021 at 6:21
-
$\begingroup$ Although this is the standard "Burton counterexample", we should note that it is not really a counterexample to Fermat's Little Theorem (see this for details). $\endgroup$ Commented Aug 29, 2022 at 12:34