# What are all positive integers n for which the congruence $a^{n+1} \equiv a (mod n)$ holds? [closed]

Fermat's little theorem says that the congruence $a^p \equiv a (mod p)$ if $p$ is a prime number. $a^{n+1} \equiv a (mod n)$ works for all integers $a$ and some positive integers $n$, how can we characterize the positive integers $n$ for which $a^{n+1} \equiv a (mod n)$ holds?

• You say a certain congruence works for all $a$ and some $n$ but do not give examples. Why not help readers by including the first few $n$ in your question? With a computer I find the only $n \leq 3000$ that work are 1, 2, 6, 42, and 1806. At oeis.org, this is A014117. – KConrad Sep 18 '14 at 13:04
• The new title is incorrect, or based on faulty understanding: search online for "Carmichael number". – Yemon Choi Sep 18 '14 at 17:46
• The question in its current form still seems to be off-topic, for the reasons given by those who voted to close. – Yemon Choi Sep 18 '14 at 17:49
• The edited question makes all the earlier comments and answers incomprehensible. This is not a good way to proceed. – Lucia Sep 18 '14 at 17:53
• Moreover this is a duplicate from mathoverflow.net/questions/37097/… – Chris Wuthrich Sep 19 '14 at 9:32

This is one of Don Zagier's problems: http://www-groups.dcs.st-and.ac.uk/~john/Zagier/Problems.html First Day 1.

I claim that this holds for $n$ if and only if $n$ is square-free and for all prime divisors $p$ of $n$, we have $p-1\mid n$.

Let $n=p_1^{k_1}\cdots p_r^{k_r}$ be the prime factor decomposition of $n$. If at least one of the $k_i$ is greater than $1$, we see that $a:=p_1\cdots p_r$ is a counter-example, since its $(n+1)$-th power will be congruent to $0$ modulo $n$. Hence $n$ must necessarily be square-free: $n=p_1\cdots p_r$. Now for any $a\in\mathbb{Z}$, the congruence $a^{n+1}\equiv a\hspace{3pt}(\mathrm{mod}\hspace{3pt}n)$ holds by definition if and only if $n\mid a^{n+1}-a$, that is, if and only if for all $i=1,\ldots,r$, $p_i\mid a(a^n-1)$. So, for each $i=1,\ldots,r$, precisely one of the two statements $p_i\mid a$ and $p_i\nmid a \wedge \mathrm{ord}_{p_i}(a)\mid n$ must be satisfied, where $\mathrm{ord}_p$ denotes the multiplicative order modulo $p$. Choosing, for $i=1,\ldots,r$, $a_i$ to be a primitive root modulo $p_i$, we see that necessarily $p_i-1\mid n$ for all $i=1,\ldots,r$, and this is sufficient as well.

• It is impossible for every prime $p$ dividing $n$ also $p-1|n$. Take the least prime divisor for example. – Konstantinos Gaitanas Sep 18 '14 at 13:39
• What about $p = 2$? – user19475 Sep 18 '14 at 13:41
• @TimoKeller i missed this case,you are right. – Konstantinos Gaitanas Sep 18 '14 at 13:43