PlanetMath: Fermat's little theorem

(more info)

Math for the people, by the people.

Main Menu

Fermat's little theorem

(Theorem)

Theorem (Fermat's little theorem) If $% latex2html id marker 196 $ a, p \in \mathbb{Z}$$ with a prime and $p \nmid a$ , then

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

If we take away the condition that $p\nmid a$ , then we have the congruence relation

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

instead.

Remarks.

Although Fermat first noticed this property, he never actually proved it. There are several different ways to directly prove this theorem, but it is really just a corollary of the Euler theorem.
More generally, this is a statement about finite fields: if is a finite field of order , then $a^{q-1}=1$ for all $0\ne a\in K$ . More succinctly, the group of units in a finite field is cyclic. If is prime, then we have Fermat's little theorem.
While it is true that prime implies the congruence relation above, the converse is false (as hypothesized by ancient Chinese mathematicians). A well-known example of this is provided by setting and $p=341=11\times 31$ . It is easy to verify that $2^{341}\equiv 2 \pmod{341}$ . A positive integer satisfying $a^{p-1}\equiv 1 \pmod{p}$ is known as a pseudoprime of base . Fermat little theorem says that every prime is a pseudoprime of any base not divisible by the prime.