Fermat's little theorem is a fundamental theorem in elementary number theory, which helps compute powers of integers modulo prime numbers. It is a special case of Euler's theorem, and is important in applications of elementary number theory, including primality testing and public-key cryptography.
The result is called Fermat's "little theorem" in order to distinguish it from Fermat's last theorem.
Let be a prime number, and be any integer. Then is always divisible by
In modular arithmetic notation, this can be written as
is prime, so is divisible by by Fermat's little theorem.
Proof using Euler's theorem:
Let be Euler's totient function. Euler's theorem says that whenever and are coprime. Let be a prime Then so for any coprime to In this case, multiplying both sides by gives as desired.
On the other hand, if is not coprime to then In this case, both and are congruent to so here as well.
Proof by induction:
First, we will show that the theorem is true for all positive integers by induction. The base case when is obviously true:
For the inductive hypothesis, assume that for a certain integer . The goal is to show that
By the binomial theorem,
But for , because but and . So the middle terms vanish mod
Substituting by the inductive hypothesis gives .
So the result holds for all positive by induction. But every integer is congruent mod to a positive integer, so the result holds for every integer.
Proof using Lagrange's theorem:
Suppose (as above, the other case is trivial). The set of powers of forms a subgroup of . Its size (or order) is the multiplicative order of ; if it is the subgroup consists of the elements By Lagrange's theorem, divides the order of which is So for some integer Then
This last proof actually generalizes to a proof of Euler's theorem.
A final proof is outlined in the following exercise:
Fermat's little theorem states that for prime , we have Here is a proof:
- Consider and
- They are permutations of each other under
However, when we are talking about a composite number , we have for coprime integers and instead, from Euler's theorem.
If I use the above proof flow for the Euler's theorem, in which step do I first make a mistake?
If and , prove that
By Fermat's little theorem, and . So and This implies
See the wiki on primitive roots for a generalization of this argument.
What is the remainder of upon division by 59?
By Fermat's little theorem, so so
Let be a prime number, and let be any positive integer Show that the decimal expansion of consists of repeating decimal digits.
By Fermat's little theorem, is divisible by say So
Since write as a -digit number (with 0s in the front if necessary). The above expansion shows that the -digit number will repeat in the decimal expansion.
For example, let and Then so So
Fermat's little theorem suggests a primality test: given pick a random small number which is coprime to and compute If this is not then is composite by Fermat's little theorem. If it is can we conclude that is prime? In general, the answer is no. For instance, and so and therefore
If is composite but for some coprime to then is called a pseudoprime to base If is a pseudoprime to every base relatively prime to it, it is called a Carmichael number. No iteration of this primality test will be able to distinguish Carmichael numbers from actual primes.