Number Theory: Fermat's little theorem

Number Theory: Fermat’s little theorem

Understanding Fermat’s Little Theorem

Fermat’s Little Theorem is a fundamental theorem in number theory, named after Pierre de Fermat.
It states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p).
The notation “≡” means “congruent to”, and a ≡ b (mod p) means that a and b have the same remainder when divided by p.
Fermat’s Little Theorem is often used as a primality test.

Applying Fermat’s Little Theorem

Fermat’s Little Theorem can be used to compute powers of integers modulo p.
Let k = q(p-1) + r, where q and r are integers and 0 ≤ r < p-1. Then a^k ≡ a^r (mod p).
This is particularly useful in cryptography, such as the RSA encryption process.

Proving Fermat’s Little Theorem

The theorem can be proved using mathematical induction, a method of mathematical proof.
A key observation is that, for a prime p and any integer a not divisible by p, the integers a, 2a, …, (p-1)a are distinct and each is congruent to one of 1, 2, …, p-1 modulo p.
This is because if ia ≡ ja (mod p) with 1 ≤ i < j ≤ p-1, then p must divide a(j-i), but this is impossible as neither a nor j-i is divisible by p.

Using Fermat’s Little Theorem in Cryptography

Many modern cryptosystems use Fermat’s Little Theorem, especially in the field of public key cryptography.
For example, the RSA algorithm uses it in both the encryption and decryption steps.
Fermat’s Little Theorem is a key pillar in the generation of public and private keys, secure transmission of data, and the decryption of the received data.

Handling Composite Numbers

Fermat’s Little Theorem doesn’t hold for composite numbers (non-primes). However, some composite numbers a do satisfy a^(n-1) ≡ 1 (mod n). These are known as Carmichael numbers, which are a type of pseudoprime.
Detecting Carmichael numbers is therefore important when using Fermat’s Little Theorem as a probabilistic primality test, as they would pass the test but are not prime.