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

Question

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?

Answer 1

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

Answer 2

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.