Associated Topics || Dr. Math Home || Search Dr. Math

Carmichael Numbers

```
Date: 10/31/97 at 12:45:54
From: Jerry TAO

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

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search