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}^{p1}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modp).$$ 
If we take away the condition that $p\mathrm{\nmid}a$, then we have the congruence relation^{}
$${a}^{p}\equiv a\phantom{\rule{veryverythickmathspace}{0ex}}(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}^{q1}=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 wellknown 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\phantom{\rule{veryverythickmathspace}{0ex}}(mod341)$. A positive integer $p$ satisfying ${a}^{p1}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(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.
References
 1 H. Stark, An Introduction to Number Theory^{}. The MIT Press (1978)
Title  Fermat’s little theorem 
Canonical name  FermatsLittleTheorem 
Date of creation  20130322 11:45:08 
Last modified on  20130322 11:45:08 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  13 
Author  CWoo (3771) 
Entry type  Theorem 
Classification  msc 1100 
Classification  msc 16E30 
Synonym  Fermat’s theorem 
Related topic  EulerFermatTheorem 
Related topic  ProofOfEulerFermatTheoremUsingLagrangesTheorem 
Related topic  FermatsTheoremProof 
Related topic  PolynomialCongruence 