Main Page | See live article | Alphabetical index

Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a,
This means that if you take some number a, multiply it by itself p times and subtract 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, dated October 18 1640 to his confidante Frenicle in the following equivalent form: p divides ap-1 - 1 whenever p is prime and a is coprime to p. The case a = 2 was known to the ancient Chinese.

Table of contents
1 Proofs
2 Generalizations
3 Pseudoprimes

Proofs

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

See Proofs of Fermat's little theorem.

Generalizations

A slight generalization of the theorem, which immediately follows from it, is as follows: if p is prime and m and n are positive integers with mn (mod p-1), then aman (mod p) for all integers a. In this form, the theorem is used to justify the RSA public key encryption method.

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

where φ(n) denotes Euler's φ function counting the integers between 1 and n that are coprime to n. This is indeed a generalization, because if n = p is a prime number, then φ(p) = p - 1.

This can be further generalized to Carmichael's theorem, stated here: " class="external">http://mathworld.wolfram.com/CarmichaelsTheorem.html.

Pseudoprimes

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