# Fermat's Little Theorem/Proof 1

## Theorem

Let $p$ be a prime number.

Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.

Then:

- $n^{p - 1} \equiv 1 \pmod p$

## Proof

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 Reduced Residue System 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$

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Theorem $\text{F}$