Table of contents |

2 Generalizations 3 Pseudoprimes |

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 *m* ≡ *n* (mod *p*-1), then *a*^{m} ≡ *a*^{n} (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

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

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 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.