Testing if a Number is Prime

It can be hard to decide if a given number is a odd prime.
By Fermat’s Theorem, if
$n$
is prime, then for any
$a$
we have
$a^{n-1} = 1 \pmod{n}$
. This suggests the Fermat test for a prime: pick a random
$a \in \{1,...,n-1\}$
and see if
$a^{n-1} = 1 \pmod{n}$
. If not, then
$n$
must be composite.
However we may still get equality even when
$n$
is not prime. For example, take
$n = 561 = 3\times 11\times 17$
. By the Chinese Remainder Theorem,
$\mathbb{Z}_{561} = \mathbb{Z}_{3} \times \mathbb{Z}_{11} \times \mathbb{Z}_{17}$

thus each
$a \in \mathbb{Z}_{561}^*$
corresponds to some
$(x,y,z) \in \mathbb{Z}_{3}^* \times \mathbb{Z}_{11}^* \times \mathbb{Z}_{17}^* .$

By Fermat’s Theorem,
$x^2 = 1$
,
$y^{10} = 1$
, and
$z^{16} = 1$
. Since 2, 10, and 16 all divide 560, this mean s
$(x,y,z)^{560} = (1,1,1)$
, in other words,
$a^{560} = 1$
for any
$a \in \mathbb{Z}_{561}^*$
.
Thus no matter what
$a$
we pick,
$561$
always passes the Fermat test despite being composite so long as
$a$
is coprime to
$n$
. Such numbers are called Carmichael numbers, and it turns out there are infinitely many of them.
If
$a$
is not coprime to
$n$
then the Fermat test fails, but then we can easily recover a factor of
$n$
by computing
$\gcd(a, n)$
.