I would like to prove the equivalence of the two most common definitions of a composite integer $n > 1$ being a Carmichael number:
$a^n \equiv a \mod n $ for all $a$ $\iff a^{n-1} \equiv 1 \mod n$ for all $a$ such that $\mathrm{gcd}(a,n)=1$. 


I do not see how to prove the right-to-left statement (that is, why if the congruence on the right holds whenever $\mathrm{gcd}(a,n)=1$ then the congruence on the left holds for all $a$). Of course if $n$ divides $a$, the congruence on the left is obvious since both terms are 0.


I would like to use the Chinese remainder theorem to try to reduce the problem to the case of a prime-power modulus $n = p^e$ (since I don't know yet $n$ must be square-free), but $a^{n-1} \equiv 1 \mod{p^e}$ is not a very helpful equation.


Every article on the web says it is obvious, but not for me. Can you help me?



equivalence of definitions of Carmichael numbers
Korselt's criterion uses that $p^n = p$ for any $p|n$, but $(p,n)=p\ne 1$, so I still don't see to get ou of this. Maybe my proof of Korselts's criterion is out of date.


