(i) Prove that for odd prime $p$ we have
$$ (\frac{-2}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 3\pmod 8 \\ -1 & \text{ if } p \equiv -1 \text{ or } -3 \pmod 8 \end{cases} $$
(ii) Prove that if the odd prime $p$ satisfies
$$ p \mid (x^2 + 2) $$
then $p ≡ 1, 3 \pmod 8$.
(iii) Factorise the following integers (−2 replaced by +2 of question 3):
(a) $18^2 + 2 = 326$
(b) $23^2 + 2 = 531$
(c) $51^2 + 2 = 2603$
(d) $27^2 + 2 = 727$
(e) $105^2 + 2 = 11027$
(f) $47^2 + 2 = 2211$
(g) $195^2 + 2 = 38027$
(i) We start with Proposition (7.15):
Let $p$ be an odd prime then
$$ (\frac{2}{p}) = \begin{cases} 1 & \text{ if } p \equiv \pm 1 \pmod 8 \\ -1 & \text{ if } p \equiv \pm 3 \pmod 8 \end{cases} $$
We note that
$$ (\frac{-2}{p}) = (\frac{2}{p}) \times (\frac{-1}{p}) $$
The following table summarises Propositions (7.11) and Propositions (7.15), with Proposition (7.11) recast to modulo 8.
| p mod 8 | (-1/p) | (2/p) | (-1/p)*(2/p) |
| 1 | 1 | 1 | 1 |
| 3 | -1 | -1 | 1 |
| -3 | 1 | -1 | -1 |
| -1 | -1 | 1 | -1 |
Since every possible case for $p$ is considered, we can read off the final column as the desired conclusion, that for odd prime $p$
$$ (\frac{-2}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 3\pmod 8 \\ -1 & \text{ if } p \equiv -1 \text{ or } -3 \pmod 8 \end{cases} $$
(ii) We start with $p \mid (x^2 + 2)$ which is equivalent to
$$ x^2 \equiv -2 \pmod p $$
We have seen from part (i) that -2 is a quadratic residue of odd prime $p$ if $p \equiv 1 \pmod 8$ or $p\equiv 3 \pmod 8$. This is the desired conclusion.
(iii) The factorisation exercises require odd primes which are congruent to 1 or 3 modulo 8. The first of these are
$$ 3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97, 107, 113, 131, 137, 139, 163, 179 $$
(a) We consider $18^2 \equiv -2 \pmod p$, where prime $p \equiv 1,3 \pmod 8$, Such a prime divides $18^2+2=326$.
We immediately see 2 is a factor. Trying the above primes up to $\lfloor \sqrt{163}\rfloor=12$ tells us that 163 is prime, and so
$326 = 2 \times 163$
(b) Trying factor 59 gives us
$ 531 = 3^2 \times 59 $
(c) Trying factor 19 gives us
$ 2603 = 19 \times 137 $
Trying the above primes up to $\lfloor \sqrt{137}\rfloor=11$ tells us that 137 is prime.
(d) Trying factors 17 and 43 gives us
$ 731 = 17 \times 43 $
(e) Trying the above primes up to $\lfloor \sqrt{11027}\rfloor=105$ tells us that 11027 is prime.
(f) trying factors 11 and 67 gives us
$ 2211 = 3 \times 11 \times 67 $
(g) Trying factor 11 gives us
$ 38027 = 11 \times 3457$
Trying the above primes up to $\lfloor \sqrt{3457}\rfloor=58$ tells us that 3457 is prime.