# 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}$

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\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.

## References

• 1 H. Stark, . The MIT Press (1978)
 Title Fermat’s little theorem Canonical name FermatsLittleTheorem Date of creation 2013-03-22 11:45:08 Last modified on 2013-03-22 11:45:08 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 13 Author CWoo (3771) Entry type Theorem Classification msc 11-00 Classification msc 16E30 Synonym Fermat’s theorem Related topic EulerFermatTheorem Related topic ProofOfEulerFermatTheoremUsingLagrangesTheorem Related topic FermatsTheoremProof Related topic PolynomialCongruence