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 Since {jatex options:inline}\mathbb{Z}_{p^k}\]
\[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.