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), 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.

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)

⇒ 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)

Using Induction

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’.

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, a², a³, …, 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.

Solved Examples