# two definitions of Carmichael numbers

• Sep 27th 2009, 12:55 AM
kobulingam
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?
• Sep 27th 2009, 07:57 AM
Media_Man
Modular Inverses
It has to do with the fact that $\displaystyle a^{-1}$ does not exist unless a and n are coprime. Consider Def 1: $\displaystyle a^n\equiv a (\bmod n)$. That means that $\displaystyle a^{n-1}\equiv a^na^{-1}\equiv aa^{-1}\equiv 1 (\bmod n)$. 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 $\displaystyle \to$ (Def 2 OR $\displaystyle gcd(a,n)\neq 1$)

Consider a concrete example. $\displaystyle 561=3*11*17$ is a Carmichael number:

$\displaystyle 2^{561}\equiv 2 (\bmod 561)$ and $\displaystyle 2^{560}\equiv 1 (\bmod 561)$ as the theory suggests.

$\displaystyle 3^{561}\equiv 3 (\bmod 561)$ but $\displaystyle 3^{560}\equiv 375 (\bmod 561)$ because 3 and 561 are not coprime.
• Sep 27th 2009, 10:18 AM
kobulingam
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.