# 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