Fermats Little Theorem

Introduction

What happens when you raise an integer to a high power and take the remainder modulo a prime? Fermat's little theorem gives a beautiful answer: for any integer a not divisible by prime p the power a(p−1) leaves remainder 1 when divided by p

This theorem, stated by Pierre de Fermat in 1640, is a cornerstone of number theory. It provides a deep connection between exponentiation and prime numbers, enabling efficient computation of modular inverses and forming the mathematical basis for RSA encryption.

Understanding Fermat's little theorem leads naturally to Euler's theorem (its generalization to composite moduli) and to modern cryptographic protocols that secure digital communication worldwide.

Statement of the Theorem

Let p be a prime number and a an integer not divisible by p (i.e., gcd(a,p)=1. Then:

a(p−1)≡1*(mod(p))

An equivalent formulation that holds for all integers a (including multiples of p):

ap≡a*(mod(p))

The two forms are equivalent when gcd(a,p)=1 dividing ap≡a by a gives a(p−1)≡1

Proof by Group Theory

The multiplicative group (ℤ/p*ℤ)∗ consists of the nonzero residue classes {1,2,…,p−1} under multiplication mod p This group has order p−1

By Lagrange's theorem, the order of any element divides the order of the group. Thus for any a with gcd(a,p)=1 the order of a divides p−1 which implies a(p−1)≡1

Proof by Counting

Consider the products a⋅1,a⋅2,…,a⋅(p−1) modulo p Since gcd(a,p)=1 these are all distinct and nonzero mod p Thus they form a permutation of {1,2,…,p−1}

Multiplying all elements together:

(a⋅1)*(a⋅2)⋯(a⋅(p−1))≡1⋅2⋯(p−1)*(mod(p))

a(p−1)⋅(p−1)!≡(p−1)!*(mod(p))

Since gcd((p−1)!,p)=1 we can cancel to get a(p−1)≡1*(mod(p))

Euler's Generalization

Euler's theorem extends Fermat's result to composite moduli. For any positive integer n and a with gcd(a,n)=1

aϕ(n)≡1*(mod(n))

where ϕ(n) is Euler's totient function—the count of integers from 1 to n that are coprime to n For prime p ϕ(p)=p−1 recovering Fermat's theorem.

Applications

RSA Cryptography

RSA encryption relies on a generalization combining Fermat's and Euler's theorems. For n=p*q (product of two primes), if we choose e,d such that e*d≡1*(mod(ϕ(n))) then:

(me)d≡m*(mod(n))

for any message m The public key (n,e) encrypts, and the private key (n,d) decrypts.

Fermat Primality Test

The contrapositive of Fermat's theorem gives a primality test: if a(n−1)≢1*(mod(n)) for some a coprime to n then n is definitely composite.

However, some composite numbers (called Carmichael numbers) satisfy a(n−1)≡1*(mod(n)) for all a coprime to n. The smallest is 561=3⋅11⋅17.

The Miller-Rabin test strengthens Fermat's test to avoid Carmichael numbers, and is used in practice for probabilistic primality testing.

Simplifying Modular Exponentiation

Fermat's theorem allows reducing large exponents before computing. To find ak*(mod(p))

1. Compute r=k*mod(p-1)

2. Then ak≡ar*(mod(p))

This dramatically reduces computation for astronomical exponents.

The Converse is False

If a(n−1)≡1*(mod(n)) we cannot conclude n is prime. For example:

2≡1*(mod(341))

but 341=11⋅31 is composite. Such n are called pseudoprimes base 2.

Connection to Other Concepts

Fermat's little theorem is a special case of Lagrange's theorem in group theory. The multiplicative group (ℤ/p*ℤ)∗ is cyclic of order p−1 and Fermat's theorem says every element's order divides the group order.

The theorem also connects to Wilson's theorem: (p−1)!≡−1*(mod(p)) for prime p Both characterize primality through modular arithmetic.

In algebraic terms, Fermat's theorem says that in the finite field (𝔽_p) every nonzero element is a root of x(p−1)−1 This polynomial has exactly p−1 roots, which accounts for all nonzero elements.

Summary

Fermat's little theorem states that for prime p and gcd(a,p)=1 we have a(p−1)≡1*(mod(p)) Equivalently, ap≡a*(mod(p)) for all integers a

The theorem follows from group theory (Lagrange's theorem applied to the multiplicative group) or from a clever counting argument. Euler's theorem aϕ(n)≡1*(mod(n)) generalizes to composite moduli.

Key applications include:

• Computing large powers modulo primes efficiently

• Finding modular inverses: a(−1)≡a(p−2)*(mod(p))

• Primality testing (Fermat and Miller-Rabin tests)

• RSA cryptography and public-key encryption

The converse fails: passing the Fermat test doesn't guarantee primality (Carmichael numbers exist). Despite this limitation, Fermat's little theorem remains one of the most useful results in number theory.