The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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,


   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!   
Associated Topics:
College Modern Algebra
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.