Fermat’s little theorem

Theorem (Fermat’s little theorem).

If $a\mathrm{,}p\mathrm{\in }\mathrm{Z}$ with $p$ a prime and $p\mathrm{\nmid }a$, then

$$a^{p-1}\equiv 1(modp).$$

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

$$a^p\equiv a(modp)$$

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 $K$ is a finite field of order $q$, 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 $q$ is prime, then we have Fermat’s little theorem.

• While it is true that $p$ 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 $a=2$ and $p=341=11\times 31$. It is easy to verify that $2^{341}\equiv 2(mod341)$. A positive integer $p$ satisfying $a^{p-1}\equiv 1(modp)$ is known as a pseudoprime of base $a$. Fermat little theorem says that every prime is a pseudoprime of any base not divisible by the prime.