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?
What are all positive integers n for which the congruence $a^{n+1} \equiv a (mod n)$ holds? [closed]

5$\begingroup$ 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. $\endgroup$– KConradSep 18, 2014 at 13:04

2$\begingroup$ The new title is incorrect, or based on faulty understanding: search online for "Carmichael number". $\endgroup$– Yemon ChoiSep 18, 2014 at 17:46

2$\begingroup$ The question in its current form still seems to be offtopic, for the reasons given by those who voted to close. $\endgroup$– Yemon ChoiSep 18, 2014 at 17:49

3$\begingroup$ The edited question makes all the earlier comments and answers incomprehensible. This is not a good way to proceed. $\endgroup$– LuciaSep 18, 2014 at 17:53

1$\begingroup$ Moreover this is a duplicate from mathoverflow.net/questions/37097/… $\endgroup$– Chris WuthrichSep 19, 2014 at 9:32
2 Answers
This is one of Don Zagier's problems: http://wwwgroups.dcs.stand.ac.uk/~john/Zagier/Problems.html First Day 1.
I claim that this holds for $n$ if and only if $n$ is squarefree and for all prime divisors $p$ of $n$, we have $p1\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 counterexample, since its $(n+1)$th power will be congruent to $0$ modulo $n$. Hence $n$ must necessarily be squarefree: $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^n1)$. 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_i1\mid n$ for all $i=1,\ldots,r$, and this is sufficient as well.

$\begingroup$ It is impossible for every prime $p$ dividing $n$ also $p1n$. Take the least prime divisor for example. $\endgroup$ Sep 18, 2014 at 13:39

$\begingroup$ What about $p = 2$? $\endgroup$– user19475Sep 18, 2014 at 13:41

$\begingroup$ @TimoKeller i missed this case,you are right. $\endgroup$ Sep 18, 2014 at 13:43