Fermat’s Little Theorem: A Cornerstone of Number Theory

Event Summary:
Fermat’s Little Theorem states that if p is a prime number and a is an integer not divisible by p, then:

a ⁽ᵖ⁻¹⁾ ≡ 1 (mod p).
Proposed by Pierre de Fermat in 1640, this deceptively simple theorem became foundational in number theory, modular arithmetic, and modern cryptography.

First Stated in a Letter (1640):
Fermat (age 33) wrote to mathematician Frénicle de Bessy that for any integer a not divisible by prime p, the expression a ⁽ᵖ⁻¹⁾ – 1 is divisible by p.

Modular Arithmetic Form:
Today, the theorem is usually written as: a⁽ᵖ⁻¹⁾ ≡ 1 mod p, meaning the remainder when a⁽ᵖ⁻¹⁾ is divided by p is 1.

Example:
Let a = 2, p = 7 :
2⁶ = 64, and 64 mod 7 = 1.
So Fermat’s theorem holds: 2⁶ ≡ 1 mod 7.

Conditions:

• p must be prime.
• a is not a multiple of p, that is gcd(a, p) = 1
  If a is multiple of p, the congruence fails.
  • gcd(a, p) = 1 means “the greatest common divisor of a and p equals 1.”

No Proof by Fermat:
Fermat offered no formal proof—typical of his style. The first known proof was given by Leonhard Euler in the 18th century.

Euler’s Generalization:
Euler extended the theorem to: a^φ(n) ≡ 1 mod n, where φ(n) is Euler’s totient function and a is coprime to n.

Used in Cryptography:
Fermat’s theorem underpins algorithms like RSA, which depend on modular exponentiation and the difficulty of factoring large primes.

A “Little” Theorem, Big Legacy:
It’s called “little” to distinguish it from Fermat’s Last Theorem, another much more famous (and difficult) conjecture.

Why It Matters:
Fermat’s Little Theorem links primes and powers in modular arithmetic. It remains vital in computer science, cryptography, and pure math.