Determine the square root of the following:
(a) $2 \pmod {17}$
(b) $16 \pmod {17}$
(c) $5 \pmod {17}$
(a) We first use Euler's Criterion (7.5) to test whether 2 is a quadratic residue of 17.
Since $17 \not \mid 2$ and $2^{\frac{17-1}{2}} \equiv 2^8 \equiv 1 \pmod {17}$ and so 2 does have a square root modulo 17.
By Proposition (7.3) $x^2 \equiv 2 \pmod {17}$ has 2 solutions.
The following calculations tell us that $x \equiv 6 \pmod {17}$ is a solution to $x^2 \equiv 2 \pmod {17}$.
| x | x^2 mod 17 |
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
| 4 | 16 |
| 5 | 8 |
| 6 | 2 |
We can use Proposition (3.14b) to identify the second solution as $x \equiv -6 \equiv 11 \pmod {17}$.
So the two square roots of $2 \pmod {17}$ are $x \equiv 6 \pmod {17}$ and $x \equiv 11 \pmod {17}$.
(b) By inspection we can see that $4^2 \equiv 16 \pmod {17}$.
By Proposition (7.3) $x^2 \equiv 16 \pmod {17}$ has 2 solutions.
We can use Proposition (3.14b) to identify the second solution as $x \equiv -4 \equiv 13 \pmod {17}$.
So the two square roots of $16 \pmod {17}$ are $x \equiv 4 \pmod {17}$ and $x \equiv 13 \pmod {17}$.
(c) We first use Euler's Criterion (7.5) to test whether 5 is a quadratic residue of 17.
Since $17 \not \mid 5$ and $5^{\frac{17-1}{2}} \equiv 5^8 \equiv -1 \pmod {17}$ and so 5 does not have a square root modulo 17.