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  
 is prime, then for any 
 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  
 must be composite.
However we may still get equality even when  
 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  
 we pick,  
 always passes the Fermat test despite being composite so long as  
 is coprime to  
. Such numbers are called Carmichael numbers, and it turns out there are infinitely many of them.
 is not coprime to  
 then the Fermat test fails, but then we can easily recover a factor of  
 by computing  
\[\gcd(a, n)\]