Last modified on February 15th, 2024

chapter outline

 

Fermat’s Little Theorem

Fermat’s little theorem (also known as Fermat’s remainder theorem) is a theorem in elementary number theory, which states that if ‘p’ is a prime number, then for any integer ‘a’ with p∤a (p does not divide a), ap – 1 ≡ 1 (mod p)

In modular arithmetic notation, 

ap ≡ a (mod p) 

⇒ ap – 1 ≡ 1 (mod p)

It is a special case of Euler’s Theorem and is also important in applications of elementary number theory, where it is used to simplify exponents.

Proof

Although a special case of Euler’s theorem, it is possible to prove Fermat’s theorem directly, using methods like induction and group theory, without relying on Euler’s theorem.

Using Euler’s Theorem

If ϕ(n) is Euler’s totient function, according to Euler’s theorem, aϕ(n) ≡ 1 (mod n), where ‘a’ and ‘n’ are coprime. 

If ‘n’ is coprime to ‘p,’ ϕ(p) = p − 1

Thus, for any value of ‘a’ coprime to ‘p,’ aϕ(p)  ≡ 1 (mod p)

⇒ ap − 1 ≡ 1 (mod p). 

On multiplying both sides by ‘a’, we get ap ≡ a (mod p)

Alternatively, if ‘a’ is not coprime to ‘p,’ then p∣a. 

Here, both ‘ap’ and ‘a’ are congruent to 0 (mod p)

Thus, ap ≡ a (mod p)

Using Induction

Base Step: When a = 1, 1p ≡ 1 (mod p)

Inductive Step: Let us assume ap ≡ 1 (mod p) for a certain integer ‘a.’

Now, considering the value (a + 1), we get

(a + 1)p ≡ a + 1 (mod p)

By the Binomial theorem, ${\left( a+1\right) ^{p}=a^{p}+\begin{pmatrix} p \\ 1 \end{pmatrix}a^{p-1}+\begin{pmatrix} p \\ 2 \end{pmatrix}a^{p-2}+\ldots +\begin{pmatrix} p \\ p-1 \end{pmatrix}a+1}$

Since ${\begin{pmatrix} p \\ k \end{pmatrix}=\dfrac{p!}{k!\left( p-k\right) !}}$

${p| \begin{pmatrix} p \\ k \end{pmatrix}}$ for 1 ≤ k ≤ p – 1

Thus, (a + 1)p ≡ ap + 1 (mod p)

Now, substituting ap ≡ a (mod p), we get (a + 1)p ≡ a + 1 (mod p)

Thus, the result holds for every integer ‘a’.

Using Group Theory (Lagrange’s Theorem)

Let us consider a group of integers modulo p under multiplication, denoted by (ℤ/pℤ)×, which consists of integers from 1 to p – 1 (coprime to ‘p’)

Let ‘a’ be an integer such that p∤a, a Є (ℤ/pℤ)×

Now, considering a subgroup H, we get H = {a, a2, a3, …, ap – 1} of (ℤ/pℤ)×

By Lagrange’s Theorem, the order of H must divide the order of (ℤ/pℤ)×, where ord((ℤ/pℤ)×) = p−1.

⇒ ord(H) | ord((ℤ/pℤ)×), where ord(H) is the smallest positive integer ‘k’ such that ak ≡ 1 (mod p)

⇒ k ≤ p – 1

Since ord(H) | p – 1 and k ≤ p – 1, ord(H) = p – 1

⇒ ap – 1 ≡ 1 (mod p), and thus Fermat’s little theorem is verified.

Solved Examples

Find the remainder of 373 (mod 11)

Solution:

By Fermat’s little theorem, we get 311 – 1 = 310 ≡ 1 (mod 11), where 11 is a prime number, and 3 and 11 are coprime numbers.
Here, 373 = (310)7 ⋅ 33 ≡ 17 ⋅ 33 ≡ 27 ≡ 5 (mod 11)
Thus, the remainder of 373 is 5 in modulo 11.

What is the remainder of 7121 on division by 31?

Solution:

By Fermat’s little theorem, we get 731 – 1 = 730 ≡ 1 (mod 31), where 31 is a prime number, and 7 and 31 are coprime numbers.
Here, 7121 = (730)4 ⋅ 7 ≡ 1 ⋅ 7 ≡ 7 (mod 31)
Thus, the remainder of 7121 upon division by 31 is 7