Home › Counting and number theory

A short proof of Fermat's little theorem

Permute the nonzero residues

If $p$ is prime and $p$ does not divide $a$ , multiplying each nonzero residue modulo $p$ by $a$ produces the same residues in a different order. Their products are congruent and can be canceled.

Problem

Prove Fermat's little theorem: if $p$ is prime and integer $a$ is not divisible by $p$ , then $a^{p - 1}$ leaves remainder 1 when divided by $p$ .

Answer

a^{p - 1}

is congruent to

1

modulo

p

The condition that p does not divide a permits cancellation modulo p.

Step-by-step solution

1. Multiply all nonzero residues

Consider $1, 2, ..., p - 1$ modulo $p$ . The residues of $a, 2 a, ..., (p - 1) a$ are all nonzero and distinct: if $aj$ and $ak$ were equal modulo $p$ , then $p$ would divide $a (j - k)$ , forcing $j = k$ in the stated range.

2. Compare the products

The two lists are permutations of one another, so $a^{p - 1} (p - 1)!$ is congruent to $(p - 1)!$ modulo $p$ .

3. Cancel

None of the factors in $(p - 1)!$ is divisible by $p$ , so the product has a multiplicative inverse modulo $p$ . Canceling it gives the claimed congruence.

Add to Chrome - solve your own

Screenshot any problem on your screen and get the steps. Chrome on a computer; free.