📂Number Theory

Proof of Fermat's Little Theorem

Theorem ¹

Prime numbers $p$ and integers $a$ that are coprime to each other, $a^{p-1} \equiv 1 \pmod{p}$

Explanation

Fermat’s little theorem is a straightforward yet highly influential theorem used in a variety of fields. Although there is a generalized theorem by Euler, Fermat’s little theorem is often sufficient. It is particularly essential in fields like cryptography that extensively deal with exponentiation in finite fields.

Proof

Strategy: The proof is brutishly simple yet not trivial. If $$ a \cdot 2a \cdot \cdots \cdot (p-1)a \equiv (p-1)! \pmod{p} $$ is established, then eliminating $(p-1)!$ from both sides would prove Fermat’s little theorem. That is, it suffices to show that two sets $\left\{ a,2a,\cdots , (p-1)a \right\}$ and $\left\{1,2,\cdots ,(p-1) \right\}$ are identical in $\pmod{p}$.

---

The set $\left\{ a,2a,\cdots , (p-1)a \right\}$ has exactly $(p-1)$ elements as a finite set. Since $a$ is coprime to $p$, the remainders when these elements are divided by $p$ will be integers between $1$ and $(p-1)$. 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. Consider two distinct elements $ia$ and $ja$ from $\left\{ a,2a,\cdots , (p-1)a \right\}$. Assuming the remainders of dividing both by $p$ are the same implies that $ia \equiv ja \pmod{p}$ holds. Since $a$ is coprime to $p$, canceling out $a$ from both sides also makes $i \equiv j \pmod{p}$ valid. However, within the set, $i$ and $j$ were integers greater than $0$ and less than $p$, thus $ia$ and $ja$ are also the same. This contradicts the assumption, indicating that the remainders when different elements are divided by $p$ are always distinct. With no duplicates among the remainders, in $\pmod{p}$, $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ holds. Moreover, since $p$ is a prime, it is coprime to $(p-1)!$. $$ (p-1)! a^{p-1} \equiv (p-1)! \pmod{p} $$ Upon eliminating $(p-1)!$ from both sides, the congruence $a^{p-1} \equiv 1 \pmod{p}$ is obtained.

■

Keep in mind the following corollaries as well.

Corollaries

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

Determining whether a number is prime can be challenging, but identifying a composite number is relatively easier. Note that the converse of Fermat’s test is not true. A counterexample that demonstrates the failure of the converse is Carmichael numbers. For instance, although $561=3 \cdot 11 \cdot 17$ is a composite, $a^{561} \equiv a \pmod{561}$ always holds.

Code

The following is an implementation of Fermat’s test in R, utilizing the method of exponentiation by squaring.

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

Below is the result of executing the code.

Fermat’s test was able to definitively catch composites such as $121$ or $341$ and correctly passed prime numbers like $1031$. However, it failed to catch Carmichael numbers such as $561$, $1105$, $1729$, and $41041$. To detect Carmichael numbers, one would need to use a method like the Miller-Rabin test.