Exercise (7.2).13

Determine the quadratic residues of the prime $p = 17$ by using the primitive root 3 modulo 17. Hence, or

otherwise, find the square roots of 13 (mod 17).

Since 3 is a primitive root of 17, then even powers of 3 are congruent to quadratic resides of 17. The following table of calculations shows $3^n \pmod {17}$ where $n$ is even.

n	3^n mod 17
2	9
4	13
6	15
8	16
10	8
12	4
14	2
16	1

We can read off that

$$ 3^4 \equiv 9^2 \equiv (\pm 9)^2\equiv 13 \pmod {17} $$

And so the square roots of 13 modulo 17 are $8 \pmod {17}$ and $9 \pmod {17}$.