Fermat's Little Theorem

Theorem

If $p$ is a prime number and $p \nmid n$, then $n^{p-1} \equiv 1 \pmod p$.

Corollary 1

If $p$ is a prime number, then $n^p \equiv n \pmod p$.

Corollary 2

If $p$ is a prime number, then:

$n^{p-1} \equiv \left[{p \nmid n}\right] \pmod p$

where $\left[{\cdots}\right]$ is Iverson's convention.

Proof 1

Consider the sequence of integers $n, 2n, 3n, \dots, (p-1)n$.

Note that none of these integers are congruent modulo $p$ to the others.

If this were the case, we would have $a n \equiv b n \pmod p$ for some $1 \le a < b \le p-1$.

Then as $\gcd \left\{{n, p}\right\} = 1$, and we can cancel the $n$, we get $a \equiv b \pmod p$ and so $a = b$.

Also, since $p \nmid n$ and $p \nmid c$, for any $1 \le c \le p-1$, then by Euclid's Lemma $p \nmid c n$ for any such $c n$, which means $c n \not \equiv 0 \pmod p$.

Thus, each integer in the sequence can be reduced modulo $p$ to exactly one of $1, 2, 3, \ldots, p-1$.

So $\left\{{1, 2, 3, \ldots, p-1}\right\}$ is the set of least positive residues modulo $p$.

So, upon taking the product of these congruences, we see that $n \times 2n \times 3n \times \dots \times (p-1)n \equiv 1 \times 2 \times 3 \times \cdots \times (p-1) \pmod p$.

This simplifies to $n^{p-1} \times (p-1)! \equiv (p-1)! \pmod p$.

Since $p \nmid (p-1)!$, we can cancel $(p-1)!$ from both sides, leaving us with $n^{p-1}\equiv 1 \pmod p$.

$\blacksquare$

Proof 2

By Prime Not Divisor then Coprime, $p \nmid n \implies p \perp n$ and Euler's Theorem can be applied.

Thus $n^{\phi \left({p}\right)} \equiv 1 \pmod p$.

But from Euler Phi Function of a Prime, $\phi \left({p}\right) = p \left({1 - \frac 1 p}\right) = p - 1$ and the result follows.

$\blacksquare$

Proof 3

From Multiplicative Group of Integers Modulo m, the group of units of the ring $\Z / p \Z$ forms a group of order $p-1$ under multiplication.

Since $p \nmid n$, the residue class of $n$ is invertible modulo $p$ and thus an element of this group.

By Order of Element Divides Order of Finite Group, we have $n^{p-1} \equiv 1 \pmod p$.

$\blacksquare$

Proof of Corollary 1

There are two cases:

• If $p \backslash n$, then $n^p \equiv 0 \equiv n \pmod p$.

• Otherwise, $p \nmid n$.

Then, by Fermat's Little Theorem, $n^{p-1} \equiv 1 \pmod p$.

Multiplying both sides by $n$, then by Congruence of Product we have $n^p \equiv n \pmod p$.

$\blacksquare$

Proof of Corollary 2

If $p \nmid n$ then from the main result $n^{p-1} \equiv 1 \pmod p$.

If $p \backslash n$ then $p \backslash n^{p-1}$ and $n^{p-1} \equiv 0 \pmod p$ by definition.

Hence the result by definition of Iverson's convention.

$\blacksquare$

Source of Name

This entry was named for Pierre de Fermat.

It dates from 1640.

Sources

• Seth Warner: Modern Algebra (1965): $\S 25$: Exercise $25.6$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Theorem $\text{F}$, Exercise $25$
• George E. Andrews: Number Theory (1971): $\S 3.1$: Exercise $10$
• George E. Andrews: Number Theory (1971): $\S 3.2$: Theorem $3.4$, Exercise $1$
• George E. Andrews: Number Theory (1971): $\S 4.1$: Example $4.2$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 42$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 19$ (mention)