Table of Contents

Last modified on February 15th, 2024

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), a^{p – 1} ≡ 1 (mod p)

In modular arithmetic notation,

a^{p} ≡ a (mod p)

⇒ a^{p – 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.

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.

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)

⇒ a^{p − 1} ≡ 1 (mod p).

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

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

Here, both ‘a^{p}’ and ‘a’ are congruent to 0 (mod p)

Thus, a^{p} ≡ a (mod p)

**Base Step: **When a = 1, 1^{p} ≡ 1 (mod p)

**Inductive Step:** Let us assume a^{p} ≡ 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} ≡ a^{p} + 1 (mod p)

Now, substituting a^{p} ≡ a (mod p), we get (a + 1)^{p} ≡ a + 1 (mod p)

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

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, a^{2}, a^{3}, …, a^{p – 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 a^{k} ≡ 1 (mod p)

⇒ k ≤ p – 1

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

⇒ a^{p – 1} ≡ 1 (mod p), and thus Fermat’s little theorem is verified.

**Find the remainder of 3 ^{73} (mod 11)**

Solution:

By Fermat’s little theorem, we get 3^{11 – 1} = 3^{10} ≡ 1 (mod 11), where 11 is a prime number, and 3 and 11 are coprime numbers.

Here, 3^{73} = (3^{10})^{7 }⋅ 3^{3} ≡ 1^{7} ⋅ 3^{3} ≡ 27 ≡ 5 (mod 11)

Thus, the remainder of 3^{73} is 5 in modulo 11.

**What is the remainder of 7 ^{121 }on division by 31?**

Solution:

By Fermat’s little theorem, we get 7^{31 – 1} = 7^{30} ≡ 1 (mod 31), where 31 is a prime number, and 7 and 31 are coprime numbers.

Here, 7^{121} = (7^{30})^{4} ⋅ 7 ≡ 1 ⋅ 7 ≡ 7 (mod 31)

Thus, the remainder of 7^{121} upon division by 31 is 7