Fermat’s little theorem
Theorem (Fermat’s little theorem).
If with a prime and , then
If we take away the condition that , then we have the congruence relation
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 is a finite field of order , then for all . More succinctly, the group of units in a finite field is cyclic. If is prime, then we have Fermat’s little theorem.
-
•
While it is true that 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 and . It is easy to verify that . A positive integer satisfying is known as a pseudoprime of base . 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 | 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 |