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 a is an integer and p is a prime (further symbolism is described in the article Congruence).

If is anot a multiple of p, 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 pexists.

Proof

The theorem can be aproved 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 p be an odd prime number and a be any integer. If is pnot a divisor of a, it follows from Fermat's little theorem that the right-hand side of the equation is a multiple of the prime . pThus one of the factors is a multiple of p.

Consequently

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

This conclusion is attributed to Leonhard Euler.


AlegsaOnline.com - 2020 / 2023 - License CC3