Thread: two definitions of Carmichael numbers

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?

It has to do with the fact that does not exist unless a and n are coprime. Consider Def 1: . That means that . This algebraic step can only be done if you require that a and n are coprime.

So technically Def 1 does NOT imply Def 2 directly. The correct statement is actually: Def 1 (Def 2 OR )

Consider a concrete example. is a Carmichael number:

and as the theory suggests.

but because 3 and 561 are not coprime.

Def 1 does imply Def 2 direcly because Def 2 includes the gcd - 1 stipulation. Def2 has to imply Def 1, otherwise these woudlnt be used as alternate definitions.