You are here
HomeFermat's little theorem
Primary tabs
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^{{p1}}\equiv 1\;\;(\mathop{{\rm mod}}p).$ 
If we take away the condition that $p\nmid a$, then we have the congruence relation
$a^{p}\equiv a\;\;(\mathop{{\rm mod}}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^{{q1}}=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 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\;\;(\mathop{{\rm mod}}341)$. A positive integer $p$ satisfying $a^{{p1}}\equiv 1\;\;(\mathop{{\rm mod}}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, An Introduction to Number Theory. The MIT Press (1978)
Mathematics Subject Classification
1100 no label found16E30 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections