I am looking up Carmichael numbers on the internet, and about half define it one way, the other half define it the other way. Both definitions follow:

(N is composite throughout discussions below)

Def 1: N is a Carmichael number iff for all integers a, a^n = a (mod n).

Def 2: N is a Car. num iff for all integers a coprime to n, a^(n-1) = 1(mod n)

I can see how Def 1 implies Def 2, but I don't get how Def 2 automatically gives Def 1. That is, I don't know why this fact is true...

Fact: If gcd(a,N) > 1, then a^N = a (mod N)

Can anyone help me?