# Fermat’s little theorem

###### Theorem (Fermat’s little theorem).

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

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

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

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

• 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\neq 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\pmod{341}$. A positive integer $p$ satisfying $a^{p-1}\equiv 1\pmod{p}$ 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.