Carmichael Numbers

Date: 10/31/97 at 12:45:54
From: Jerry TAO
Subject: About Carmichael number

Why must a Carmichael number be the product of at least three
distinct primes? Why is n a Carmichael number iff (p-1) divides (n-1) 
for every prime p dividing n?  I understand why a Carmichael number 
must be square free.  Thanks.

Date: 10/31/97 at 13:47:51
From: Doctor Rob
Subject: Re: About Carmichael number

Let G(N) be the multiplicative group of units modulo N. The Carmichael 
function lambda(N) is the exponent of this group; that is, the 
smallest number e such that a^e = 1 (mod N) for all a in G(N).  
A Carmichael number is defined as a composite number N for which 
lambda(N) divides N-1.

If prime p|N, then it is true that for every b in G(N), b^(p-1) = 1
(mod p), and there exists at least one b such that p-1 is the minimum
positive exponent that works. Such b's are called primitive roots
modulo p, and there are phi(p-1) of them.  Then b^(p-1) = 1 (mod p),
and we are picking b to be a primitive root modulo p.  Now find a in
G(N) such that a = b (mod p) and a = 1 (mod N/p), which you can do by
using the Chinese Remainder Theorem.  (Note that GCD(p,N/p) = 1 since
N is squarefree.)  Then a is also a primitive root modulo p.

Now a^lambda(N) = 1 (mod N) implies a^(N-1) = 1 (mod N) (since
lambda(N)|N-1), which implies that a^(N-1) = 1 (mod p) (since p|N).  
Together with the last paragraph, this implies that
a^[s*(p-1)+t*(N-1)] = 1 (mod p), for all integers s and t, so
a^GCD(p-1,N-1) = 1 (mod p) (since GCD(u,v) = s*u+t*v for some integers 
s and t).  But 0 < GCD(p-1,N-1) <= p-1, and p-1 is minimal, so 
GCD(p-1,N-1) = p-1, so p-1|N-1.

Suppose now that N = p*q, 1 < p < q. We know that q-1|N-1.
Write N = d*(q-1) + 1 = p*q, with d > 1 (since p > 1).
Reducing modulo q, d = 1 (mod q). Write d = e*q + 1, with
e > 1 (since d > 1), so

   N = (e*q+1)*(q-1) + 1 = e*q^2 - e*q + q = (e*q-e+1)*q,

so

   p = e*(q-1) + 1 > e*(p-1) + 1 > (p-1) + 1 = p,

since q > p and e > 1, a contradiction.

This contradiction means that no Carmichael number N can be of the 
form N = p*q, 1 < p < q.

You are aware that Carmichael numbers must be squarefree. The
definition prohibits Carmichael number from being prime. The only 
remaining possibility is that they are the product of at least three 
distinct primes. Examples with exactly three distinct primes are many, 
the smallest being 561 = 3*11*17.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/