|
|
|
|
Fermat's little theorem
|
(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\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 \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.
- 1
- H. Stark, An Introduction to Number Theory. The MIT Press (1978)
|
"Fermat's little theorem" is owned by CWoo. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: divisible, base, pseudoprime, integer, positive, converse, implies, cyclic, group of units, order, finite fields, Euler theorem, property, congruence relation, prime, theorem
There are 21 references to this entry.
This is version 8 of Fermat's little theorem, born on 2001-10-15, modified 2008-05-30.
Object id is 195, canonical name is FermatsLittleTheorem.
Accessed 18566 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
