- #1
- 19,865
- 10,859
Definition/Summary
Fermat's little theorem states that if p is a prime number, then for any integer a, a^{p}-a will be divisible by
Equations
a^{p-1}\equiv1\pmod p \quad (\text{for\ }a \not\equiv 0 \pmod p)
a^p\equiv a\pmod p
Extended explanation
Fermat's Little Theorem
If p is a prime number and a an integer, then
a^p\equiv a\ (p)
In order to prove Fermat's Little theorem, we will start by proving a superficially slightly weaker result, which is also referred to as Fermat's Little Theorem, on occasion. The two results imply each other, however.
Theorem
Let a and p be coprime, then
a^{p-1}-1 \equiv 0\ (p).
Proof
Start by listing the first p-1 positive multiples of a:
a, 2a, 3a, \ldots, (p -1)a
Suppose that ra and sa are the same modulo p, with 0 <r,s < p. Since a is nonzero mod p, we can cancel, giving r \equiv s\ (p). So the p-1 multiples of a above are distinct and nonzero; that is, they must be congruent to 1, 2, 3, \ldots, p-1 in some order. Multiply all these congruences together and we find
a2a3a\ldots (p-1)a \equiv 1.2.3\ldots(p-1)\ (p)
or better,
a^{p-1}(p-1)! \equiv\ (p-1)! (mod p).
Divide both side by (p-1)! to complete the proof.
Remark
This result can be proven by appeal to Lagrange's theorem, since the non-zero residues form a group modulo p. Although we haven't proven, they are a group, we are explicitly using that multiplicative inverses modulo p exist, which is an elementary application of Euclid's algorithm.
Corollary
Let p be a prime and a any integer, then a^p \equiv a\ (p).
Proof
The result is trival (both sides are zero) if p divides a. If not then we need only multiply the congruence in Fermat's Little Theorem by a to complete the proof.
* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!
Fermat's little theorem states that if p is a prime number, then for any integer a, a^{p}-a will be divisible by
Equations
a^{p-1}\equiv1\pmod p \quad (\text{for\ }a \not\equiv 0 \pmod p)
a^p\equiv a\pmod p
Extended explanation
Fermat's Little Theorem
If p is a prime number and a an integer, then
a^p\equiv a\ (p)
In order to prove Fermat's Little theorem, we will start by proving a superficially slightly weaker result, which is also referred to as Fermat's Little Theorem, on occasion. The two results imply each other, however.
Theorem
Let a and p be coprime, then
a^{p-1}-1 \equiv 0\ (p).
Proof
Start by listing the first p-1 positive multiples of a:
a, 2a, 3a, \ldots, (p -1)a
Suppose that ra and sa are the same modulo p, with 0 <r,s < p. Since a is nonzero mod p, we can cancel, giving r \equiv s\ (p). So the p-1 multiples of a above are distinct and nonzero; that is, they must be congruent to 1, 2, 3, \ldots, p-1 in some order. Multiply all these congruences together and we find
a2a3a\ldots (p-1)a \equiv 1.2.3\ldots(p-1)\ (p)
or better,
a^{p-1}(p-1)! \equiv\ (p-1)! (mod p).
Divide both side by (p-1)! to complete the proof.
Remark
This result can be proven by appeal to Lagrange's theorem, since the non-zero residues form a group modulo p. Although we haven't proven, they are a group, we are explicitly using that multiplicative inverses modulo p exist, which is an elementary application of Euclid's algorithm.
Corollary
Let p be a prime and a any integer, then a^p \equiv a\ (p).
Proof
The result is trival (both sides are zero) if p divides a. If not then we need only multiply the congruence in Fermat's Little Theorem by a to complete the proof.
* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!