📂Number Theory

Proof of Fermat's Little Theorem

Theorem¹

For a prime $p$ and an integer $a$ coprime to it, $a^{p-1} \equiv 1 \pmod{p}$

Explanation

Fermat’s little theorem is simple, yet it is one of the theorems used in a great many places. Although there is also the theorem generalized by Euler, Fermat’s little theorem is often sufficient. In particular, it is an essential theorem in cryptography and the like, which deal extensively with exponentiation over finite fields.

Proof

Strategy: The proof is brute-force, but not correspondingly simple. If $$ a \cdot 2a \cdot \cdots \cdot (p-1)a \equiv (p-1)! \pmod{p} $$ holds, then by canceling $(p-1)!$ from both sides we could prove Fermat’s little theorem. In other words, it suffices to show that the two sets $\left\{ a,2a,\cdots , (p-1)a \right\}$ and $\left\{1,2,\cdots ,(p-1) \right\}$ are equal $\pmod{p}$.

---

The set $\left\{ a,2a,\cdots , (p-1)a \right\}$ is a finite set with exactly $(p-1)$ elements. Since $a$ is coprime to $p$, the remainders of these elements upon division by $p$ will each be one of the integers from $1$ to $(p-1)$. And if there are no duplicates among those remainders, then $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ will hold. Take any two distinct elements $ia$ and $ja$ from $\left\{ a,2a,\cdots , (p-1)a \right\}$ and consider them. If we assume that their remainders upon division by $p$ are equal, then $ia \equiv ja \pmod{p}$ holds. Since $a$ is coprime to $p$, canceling $a$ from both sides gives $i \equiv j \pmod{p}$ as well. But in the set above, $i$ and $j$ were integers greater than $0$ and less than $p$, so $ia$ and $ja$ are also equal. This contradicts the assumption, so we can see that the remainders of any two distinct elements upon division by $p$ are always different. Since there are no duplicates among the remainders, $\pmod{p}$ we have $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ Meanwhile, since $p$ is prime, it is coprime to $(p-1)!$. $$ (p-1)! a^{p-1} \equiv (p-1)! \pmod{p} $$ Canceling $(p-1)!$ from both sides yields the congruence $a^{p-1} \equiv 1 \pmod{p}$.

■

Let us also keep the following corollaries in mind.

Corollaries

• [1] Inverse: In $\pmod{p}$, the multiplicative inverse of $a$ is necessarily given as follows. $$ a^{-1} \equiv a^{p-2} \pmod{p} $$
• [2] Fermat test: If $a^n \equiv a \pmod{n}$ does not hold, then $n$ is composite.

Determining whether a number is prime is not easy, but determining that it is composite is relatively easy. What must be noted is that the converse of the Fermat test does not hold. In particular, a counterexample showing that the converse fails is given by the Carmichael numbers. As an example of a Carmichael number, $561=3 \cdot 11 \cdot 17$ is composite, yet $a^{561} \equiv a \pmod{561}$ always holds.

Code

The following is an implementation of the Fermat test in R, where the method of successive squaring was used for the computation.

FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
  i<-0
  if (power<0) {
    while((base*i)%%mod != 1) {i=i+1}
    base<-i
    power<-(-power)}
  
  if (power==0) {return(1)}
  if (power==1) {return(base%%mod)}
  
  n<-0
  while(power>=2^n) {n=n+1}
  
  A<-rep(1,n)
  A[1]=base
  
  for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
  
  for(i in n:1) {
    if(power>=2^(i-1)) {power=power-2^(i-1)}
    else {A[i]=1} }
  
  for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
  
  return(A[1])
}
 
fermat.test<-function(n)
{
  for(i in 2:(n-1))  {if( i!=FPM(i,n,n) ) {return(paste(i,"is a Fermat witness!"))}}
  paste(n,"passes the Fermat test!")
}
 
fermat.test(121)
fermat.test(341)    #Almost composite yields fermat witness 2, but 341=11*31 doesn't.
fermat.test(561)    #Carmicheal number 561 = 3*11*17
fermat.test(1031)    #1031 is a prime
fermat.test(1105)    #Carmicheal number 1105 = 5*13*17
fermat.test(1729)    #Carmicheal number 1729 = 7*13*19
fermat.test(41041)    #Carmicheal number 41041 = 7*11*13*41

The following is the result of running the code.

The Fermat test could reliably catch composite numbers such as $121$ or $341$, and it correctly passed primes like $1031$. However, it could not catch Carmichael numbers such as $561$, $1105$, $1729$, and $41041$. To catch Carmichael numbers, methods such as the Miller–Rabin test must be employed.