Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a,

a^p = a (mod p).

This means that if you you take some number a, multiply it by itself p times and substract a, the result is divisible by p (see modular arithmetic). It is called Fermat's little theorem to differentiate it from Fermat's last theorem. Pierre de Fermat found the theorem around 1636; it appeared in one of his letters 1640 in the following form: p divides a^p-1 - 1 whenever p is prime and a is coprime to p.

Proof

Fermat explained his theorem without a proof. The first one who gave a proof was Leibniz in his manuscipt without a date, where he wrote also that he knew a proof even before 1683.

Proving the "Little Theorem" is straightforward and elemental: we can use mathematical induction. First, the theorem is true for a=1, then one proves that that if it is true for a = k, it is also true for a = k + 1, concluding that the theorem is true for all a.

Before the main argument the following lemma is needed

(a + b)^p mod p = a^p + b^p mod p

when p is prime. The Binomial theorem tells us that

(a + b)ⁿ = ∑_i=0^p (pCi)aⁱb^p-i = a^p + b^p + ∑_i=1^p-1 (pCi)aⁱb^p-i .

Here pCi = p(p - 1)(p - 2)(p - 3) ... (p - (i-1)) / i! if 0 < i < p. Since i is less than p, and p is prime, p cannot be divided by i!, so the whole term (pCi)aⁱb^p-i is a multiple of p if 0 < i < p. This means the whole sum from i = 1 to i = p - 1 equals 0 mod p. So, (a + b)^p mod p indeed equals a^p + b^p mod p when p is prime.

Back to the proof. We proceed now with the two induction steps.

1. Obviously, when a = 1, a^p mod p = a.
2. We assume for now that when a = k, the theorem is true, that is, we assume that k^p mod p = k if k < p, and see what happens when a = k + 1:

(k + 1)^p mod p =

(by the statement shown above)

k^p + 1^p mod p = k^p + 1 mod p.

Since we assumed that k^p mod p = k if k < p, we conclude that (k + 1)^p mod p = k + 1 if k + 1 < p, which is what we wanted to demonstrate.

Generalizations

Fermat's little theorem was generalized by Euler: for any modulus n and any integer a that coprime to n, we have

a^φ(n) = 1 mod n,

where φ(n) denotes Euler's φ function counting the integers between 1 and n that are coprime to n.

This theorem can be seen as a consequence of the theorem of Lagrange, applied to the multiplicative group consisting of the residue classes mod n that are coprime to n. Or it can be proven directly: multiplication by a permutes the residue classes mod n that are coprime to n; in other words (writing R for the set of all such classes) the sets { x : x in R } and { ax : x in R } are equal; therefore, their products are equal. Hence, P = a^φ(n)P (mod n) where P is the first of those products. Since P is coprime to n, it follows that a^φ(n) = 1 (mod n).

Pseudo primes

If a and p are coprime numbers such that a^p-1 - 1 is divisible by p, then p need not be prime. If it is not, then p is called a pseudo prime to base a. A number p that is a pseudo prime to base a for every number a coprime to p is called a Carmichael number.