Page 304 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 283

cannot distinguish between primes and pseudoprimes just by choosing sufficiently many bases,
because there are composite integers n that pass all tests with bases b such that gcd(b, n) = 1.
This leads to Definition 2.

DEFINITION 2 A composite integern that satisfies the congruenceb n−1 ≡ 1 (modn) for all positive integersb
with gcd(b, n) = 1 is called a Carmichael number. (These numbers are named after Robert
Carmichael, who studied them in the early twentieth century.)

EXAMPLE 11 The integer 561 is a Carmichael number. To see this, first note that 561 is composite be-
cause 561 = 3 · 11 · 17. Next, note that if gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) =
gcd(b, 17) = 1.
Using Fermat’s little theorem we find that

2
b ≡ 1 (mod 3), b 10 ≡ 1 (mod 11), and b 16 ≡ 1 (mod 17).
It follows that

2 280
b 560 = (b ) ≡ 1 (mod 3),
10 56
b 560 = (b ) ≡ 1 (mod 11),
16 35
b 560 = (b ) ≡ 1 (mod 17).
By Exercise 29, it follows that b 560 ≡ 1 (mod 561) for all positive integers b with gcd(b, 561) =
1. Hence 561 is a Carmichael number. ▲
Although there are infinitely many Carmichael numbers, more delicate tests, described in
the exercise set, can be devised that can be used as the basis for efficient probabilistic primality
tests. Such tests can be used to quickly show that it is almost certainly the case that a given
integer is prime. More precisely, if an integer is not prime, then the probability that it passes a
series of tests is close to 0. We will describe such a test in Chapter 7 and discuss the notions
from probability theory that this test relies on. These probabilistic primality tests can be used,
and are used, to find large primes extremely rapidly on computers.

Primitive Roots and Discrete Logarithms

y
In the set of positive real numbers, if b> 1, and x = b , we say that y is the logarithm of x to
the base b. Here, we will show that we can also define the concept of logarithms modulo p of
positive integers where p is a prime. Before we do so, we need a definition.

DEFINITION 3 A primitive root modulo a prime p is an integer r in Z p such that every nonzero element of
Z p is a power of r.

ROBERT DANIEL CARMICHAEL (1879–1967) Robert Daniel Carmichael was born in Alabama. He re-
ceived his undergraduate degree from Lineville College in 1898 and his Ph.D. in 1911 from Princeton.
Carmichael held positions at Indiana University from 1911 until 1915 and at the University of Illinois from
1915 until 1947. Carmichael was an active researcher in a wide variety of areas, including number theory, real
analysis, differential equations, mathematical physics, and group theory. His Ph.D. thesis, written under the
direction of G. D. Birkhoff, is considered the first significantAmerican contribution to the subject of differential
equations.