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
-
4$\begingroup$ en.wikipedia.org/wiki/Carmichael_number $\endgroup$Will Jagy– Will Jagy2016-02-09 03:37:46 +00:00Commented 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 Engler– Hans Engler2016-02-09 03:40:14 +00:00Commented 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$reuns– reuns2016-02-09 04:41:23 +00:00Commented 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 Dubuque– Bill Dubuque2019-12-20 21:13:47 +00:00Commented 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.
$\begingroup$
$\endgroup$
2
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$.
-
2$\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$Sayan Dutta– Sayan Dutta2022-08-29 12:34:17 +00:00Commented Aug 29, 2022 at 12:34
-
$\begingroup$ $341=11\cdot31$ is a pseudoprime to the base 2. Carmichael numbers are for all bases $a$, and the smallest Carmichael number is $561=3\cdot11\cdot17$. $\endgroup$rosshjb– rosshjb2024-12-19 14:49:18 +00:00Commented Dec 19, 2024 at 14:49