Encyclopedia > Fermat's little theorem

  Article Content

Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a,
<math>a^p = a \pmod{p}</math>
This means that if you 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.


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.


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

<math>a^{\varphi (n)} = 1 \pmod{n}</math>
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: http://mathworld.wolfram.com/CarmichaelsTheorem.


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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Great River, New York

... people, 509 households, and 417 families residing in the town. The population density is 129.8/km² (336.2/mi²). There are 519 housing units at an averag ...

This page was created in 23.2 ms