Carmichael numbers are composite numbers that almost always fool the Fermat primality test. We can show that Carmichael numbers must have certain properties.
First we show they cannot be of the form
$n = p q$
where
$p, q$
are distinct primes with
$p \gt q$
. By the Chinese Remainder Theorem we have
$\mathbb{Z}_{n} = \mathbb{Z}_p \times \mathbb{Z}_q$
. Then
$n - 1 = p q - 1 = q(p - 1) + q - 1$
.
Suppose
$a$
is not a multiple of
$p$
. Then
$a^{n-1} = (a^{p-1})^q a^{q-1} = a^{q-1} \pmod p$
(by Fermat we have
$a^{p-1} = 1 \pmod p). Then if {jatex options:inline}a$
passes the Fermat test, we must have
$a^{q-1} = 1 \pmod p$
and hence
$a^d = 1$
. where
$d = \gcd(p-1,q-1)$
. Since
$\mathbb{Z}_p^*$
is cyclic, there are exactly
$d$
choices for
$a$
that satisfy
$a^d = 1$
.
Since
$q$
is strictly smaller than
$p$
. the greatest common divisor of
$p-1$
and
$q-1$
is at most
$(p-1)/2$
. Thus at most half the choices for
$a$
can fool the Fermat test. For primes
$p,q$
used in RSA,
$d$
is small with high probability, so the product
$p q$
will almost never fool the Fermat test, as mentioned earlier.
Next suppose
$n$
is not squarefree, that is
$n = p^k r$
for some prime
$p$
and
$k\ge 2$
. Then by the Chinese Remainder Theorem,
$\mathbb{Z}_n = \mathbb{Z}_{p^k} \times \mathbb{Z}_r$
. Any
$a \in \mathbb{Z}_{p^k}$
satisfies
$a^{\phi(p^k)} = 1$
by Euler’s Theorem, so if
$a^{n-1} = 1$
as well, then we must have
$a^d = 1$
where
$d = \gcd(n-1, \phi(p^k)) = \gcd(p^k r - 1, p^{k-1}(p-1)) . Since {jatex options:inline}\mathbb{Z}_{p^k}$
. is cyclic, exactly
$d$
elements
$a \in \mathbb{Z}_{p^k}$
satisfy
$a^d = 1$
. As
$p$
cannot divide
$p^k r - 1$
. the largest possible value for
$d$
is
$p-1$
. giving an upper bound of
$(p-1) / (p^{k} - 1) \le 1/4$
probability that
$n$
will pass the Fermat test.
Hence if
$n$
is a Carmichael number, then
$n$
is squarefree and is the product of at least three distinct primes.