Testing if a Number is 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)\]
.
