Prove the following for prime $p$ where $p \not \mid 7$:
$$ (\frac{7}{p}) = 1 \quad \text{if } p \equiv \pm 1, \pm 3, \pm 9 \pmod {28} $$
Factorise the following:
(a) $120^2− 7 = 14393$
(b) $354^2− 7 = 125309$
We consider the six cases $p \equiv \pm 1, \pm 3, \pm 9 \pmod {28}$.
Case $p \equiv 1 \pmod {28}$
We write $p=28k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k + 1}) = (\frac{28k + 1}{7}) = (\frac{1}{7}) = 1 $$
Case $p \equiv -1 \pmod {28}$
We write $p=28k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k - 1}) = -(\frac{28k - 1}{7}) =-(\frac{-1}{7}) = -(-1)= 1 $$
Case $p \equiv 3 \pmod {28}$
We write $p=28k + 3 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k + 3}) = -(\frac{28k + 3}{7}) = -(\frac{3}{7}) =+(\frac{7}{3})= -(\frac{1}{3}) = 1 $$
Case $p \equiv -3 \pmod {28}$
We write $p=28k + 3 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k - 3}) = (\frac{28k - 3}{7}) = (\frac{2^2}{7}) = 1 $$
Case $p \equiv 9 \pmod {28}$
We write $p=28k + 9 $ for some integer $k$. Then, using Corollary (7.17) and Proposition (7.15),
$$ (\frac{7}{p}) = (\frac{7}{28k + 9}) = (\frac{28k +9 }{7}) = (\frac{2}{7}) = 1 $$
Case $p \equiv -9 \pmod {28}$
We write $p=28k + 9 $ for some integer $k$. Then, using Corollary (7.17) and Proposition (7.15),
$$ (\frac{7}{p}) = (\frac{7}{28k - 9}) = -(\frac{28k -9 }{7}) = -(\frac{5}{7}) = -(\frac{7}{5}) = -(\frac{2}{5})= -(-1) = 1 $$
All the cases confirm that for prime $p$ where $p \not \mid 7$:
$$ (\frac{7}{p}) = 1 \quad \text{if } p \equiv \pm 1, \pm 3, \pm 9 \pmod {28} $$
A prime factor $p$ of $x^2-7$ means $x^2 \equiv 7 \pmod p$. We have just shown that $p \equiv \pm 1, \pm 3, \pm 9 \pmod {28}$. The first of such primes are
$$ 3, 19, 29, 31, 37, 47, 53, 59, 83, 103, 109, 113, 131, 137, 139, 149, 167, 193, 197, 199 $$
(a) Trying factor 37 gives
$ 14393 = 37 \times 389 $
Trying prime factors up to $\lfloor \sqrt{389} \rfloor = 19$ tells us 389 is prime.
(b) Trying factors 29 amd 149 gives
$125309 = 29^2 \times 149 $