(i) Prove that 2 is a quadratic residue of prime $p$ if and only if $p \equiv \pm 1 \pmod 8$.
(ii) Factorise the following integers:
(a) $18^2 -2 = 322$
(b) $23^2 -2 = 527$
(c) $51^2 -2 = 2599$
(d) $27^2 -2 = 727$
(e) $105^2 -2 = 11023$
(f) $47^2 -2 = 2207$
(g) $195^2 -2 = 38023$
(i) We need to prove to implications:
- 2 is a quadratic residue of $p$ $\impliedby$ $p \equiv \pm 1 \pmod 8$
- 2 is a quadratic residue of $p$ $\implies$ $p \equiv \pm 1 \pmod 8$
($\impliedby$)
We use Proposition (7.15).
Let $p$ be an odd prime. Then
$$ (\frac{2}{p}) = \begin{cases} 1 & \text{ if } p ≡ ±1 \pmod 8 \\ −1 & \text{ if } p ≡ ±3 \pmod 8 \end{cases}$$
This tells us that if $p \equiv \pm 1 \pmod 8$ then 2 is a quadratic residue of $p$.
($\implies$)
We contrapositive of the statement we want to prove is
$$p \not \equiv \pm 1 \pmod 8 \implies 2 \text{ is a not a quadratic residue of } p$$
Since $p$ is odd, and $p \not \equiv \pm 1 \pmod 8$, then the only remaining possibilities for $p$ are $p \equiv \pm 3 \pmod 8$.
By Proposition (7.15) we conclude that 2 is not a quadratic residue of $p$.
By proving the contrapositive, we have proved the intended statement that 2 is a quadratic residue of $p$ $\implies$ $p \equiv \pm 1 \pmod 8$.
Proving both implications means have have proved the statement that
$$ 2 \text{ is a quadratic residue of prime } p \iff p \equiv \pm 1 \pmod 8 $$
(ii) In the following exercises we will use primes $p$ such that $p \equiv \pm 1 \pmod 8$. The first of these are
$$ 7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97 $$
(a) We consider $18^2 \equiv 2 \pmod p$, where prime $p \equiv \pm 1 \pmod 8$. Such a prime $p$ divides $18^2-2$.
Trying factor 7 gives us
$ 322 = 2 \times 7 \times 23 $
(b) Trying factor 17 gives us
$ 527 = 17 \times 31 $
(c) Trying factor 23 gives us
$ 2599 = 23 \times 113 $
(d) Trying factors up to $\lfloor \sqrt{727}\rfloor = 26$ tells us 727 is prime.
(e) Trying factor 73 gives us
$ 11023 = 73 \times 151 $
(f) Trying factors up to $\lfloor \sqrt{2207} \rfloor = 46$ tells us 2207 is prime.
(g) Trying factor 47 gives us
$ 38023 = 47 \times 809 $
Trying factors up to $\lfloor \sqrt{809} \rfloor = 28$ tells us 809 is prime and so can't be decomposed further.