The following table shows some of the odd primes for which 5 is a quadratic residue and quadratic non-residue:
| prime p | 3 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 |
| (5/p) | -1 | -1 | 1 | -1 | -1 | 1 | -1 | 1 | 1 |
(i) Predict the congruence describing the primes for which 5 is a quadratic residue and the primes for which 5 is a quadratic non-residue. Prove your predicted formula.
(ii) Factorise the following integers:
(a) $104^2 − 5 = 10 811$
(b) $504^2 − 5 = 254 011$
(i) The table suggests the congruence describing the primes for which 5 is a quadratic residue or not is
$$ (\frac{5}{p}) = \begin{cases} 1& p \equiv \pm 1 \pmod {10} \\ -1 & p \equiv \pm 3 \pmod {10} \end{cases}$$
We'll consider the four cases, $p \equiv \pm 1 \pmod {10}$ and $p \equiv \pm 3 \pmod {10}$, in turn. There are no other cases as $p=10k+x$ where $x$ is not $\pm1$ or $\pm3$ would mean $p$ is not prime.
Case $p \equiv 1 \pmod {10}$
We write $p=10k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{5}{p}) = (\frac{5}{10k + 1}) = (\frac{10k + 1}{5}) = (\frac{1}{5}) = 1 $$
Case $p \equiv -1 \pmod {10}$
We write $p=10k - 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{5}{p}) = (\frac{5}{10k - 1}) = (\frac{10k - 1}{5}) = (\frac{-1}{5}) = (\frac{2^2}{5}) = 1 $$
Case $p \equiv 3 \pmod {10}$
We write $p=10k + 3 $ for some integer $k$. Then, using Corollary (7.17), and Proposition (7.15),
$$ (\frac{5}{p}) = (\frac{5}{10k + 3}) = (\frac{10k + 3}{5}) = (\frac{3}{5}) = (\frac{5}{3}) = (\frac{2}{3}) = -1 $$
Case $p \equiv -3 \pmod {10}$
We write $p=10k + 3 $ for some integer $k$. Then, using Corollary (7.17), and Proposition (7.15),
$$ (\frac{5}{p}) = (\frac{5}{10k - 3}) = (\frac{10k - 3}{5}) = (\frac{-3}{5}) = (\frac{2}{3}) = -1 $$
These four cases have shown that
$$ (\frac{5}{p}) = \begin{cases} 1& p \equiv \pm 1 \pmod {10} \\ -1 & p \equiv \pm 3 \pmod {10} \end{cases}$$
(ii) A prime factor $p$ of $x^2-5$ means $x^2 \equiv 5 \pmod p$. We have just shown that $p \equiv \pm 1 \pmod {10}$. The first of such primes are
$$ 11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251, 269 $$
(a) Trying factor 19 gives us
$10811 = 19 \times 569$
Trying factors up to $\lfloor \sqrt{569}\rfloor = 23$ tells us 569 is prime.
(b) Trying factors 19 and 29 gives us
$254011 = 19x29 × 461$
Trying factors up to $\lfloor \sqrt{461}\rfloor = 21$ tells us 461 is prime.