What is Fermat's little theorem

[Greg Bernhardt]

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!

 

[fresh_42]

For further information:
https://en.wikipedia.org/wiki/Fermat's_little_theorem
https://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem