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?