# Fermat's little theorem

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

*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

*a*

^{p-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 |

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

*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[1].

## Pseudoprimes

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.