Fermat's little theorem

Fermat's little theorem, or "little Fermat" for short, is a theorem of number theory. It makes a statement about the properties of prime numbers and was established in the 17th century by Pierre de Fermat. The theorem describes the universally valid congruence:

$a^{p}\equiv a{\pmod {p}},$

where is an integer and is a prime (further symbolism is described in the article Congruence).

If is not a multiple of , the result can be converted to the commonly used form

$a^{{p-1}}\equiv 1{\pmod {p}}$

since then the multiplicative inverse $a^{-1}$ modulo exists.

Proof

The theorem can be proved by induction over or as a special case of Lagrange's theorem from group theory. The latter says that every group element exponentiated by the (finite) group order yields the one-element.

See: Proofs of Fermat's little theorem in the proof archive.

Conclusion by Euler

The 3rd binomial formula states:

$(a^{{{\frac {p-1}{2}}}}-1)\cdot (a^{{{\frac {p-1}{2}}}}+1)=a^{{p-1}}-1$

Now let be an odd prime number and be any integer. If is not a divisor of , it follows from Fermat's little theorem that the right-hand side of the equation is a multiple of the prime . Thus one of the factors is a multiple of .

Consequently

$a^{{{\frac {p-1}{2}}}}\equiv \pm 1{\pmod {p}}$

This conclusion is attributed to Leonhard Euler.

Fermat's little theorem

Proof

Conclusion by Euler

Search by letter