TAOCP 1.2.4 Exercise 26

Let $p$ be an odd prime, $a$ any integer, and define $b = a^{(p-1)/2}.$ We are asked to show that $b \bmod p$ is either $0$, $1$, or $p-1$.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 26. [M15] Let $p$ be an odd prime number, let $a$ be any integer, and let $b = a^{(p-1)/2}$. Show that $b \bmod p$ is either 0 or 1 or $p-1$. [Hint: Consider $(b+1)(b-1)$.]

Verified: yes
Solve time: 1m03s

Solution

Let $p$ be an odd prime, $a$ any integer, and define

$b = a^{(p-1)/2}.$

We are asked to show that $b \bmod p$ is either $0$, $1$, or $p-1$.

If $a \bmod p = 0$, then $a$ is a multiple of $p$, so

$b = a^{(p-1)/2} \equiv 0 \pmod p,$

and the statement holds. Hence we may assume $a \perp p$, that is, $a \bmod p \ne 0$.

Consider the product

$(b+1)(b-1) = b^2 - 1 = a^{p-1} - 1.$

By Theorem F (Fermat's theorem), since $a \perp p$, we have

$a^p \equiv a \pmod p,$

so dividing both sides by $a$ (allowed by Law B, since $a \perp p$) gives

$a^{p-1} \equiv 1 \pmod p.$

Therefore

$(b+1)(b-1) = a^{p-1} - 1 \equiv 0 \pmod p.$

Thus $p$ divides the product $(b-1)(b+1)$. Since $p$ is prime, it must divide at least one of the factors. Consequently,

$b \equiv 1 \pmod p \quad \text{or} \quad b \equiv -1 \pmod p.$

Recalling that $-1 \bmod p = p-1$, we obtain the remaining two possibilities.

Combining this with the case $b \equiv 0 \pmod p$, we conclude that

$b \bmod p \in {0, 1, p-1}.$

This completes the proof.

∎