Exercise (7.4).5

Prove that for prime $p > 3$ we have

$$ (\frac{-3}{p}) = \begin{cases} (1 & \text{ if } p \equiv 1 \pmod {6}  \\ -1 & \text{ if } p \equiv 5 \pmod {6}  \end{cases}$$

Determine the prime factorisation of the following:

(a) $104^2 + 3 = 10 819$

(b) $236^2 + 3 = 55 699$

(c) $362^2 + 3 = 131 047$

We remember that the Legendre Symbol is multiplicative (Proposition 7.9)(c). This tells us

$$ (\frac{-3}{p}) = (\frac{-1}{p}) \times (\frac{3}{p}) $$

Proposition (7.11) tells us, for an odd prime $p$,

$$ (\frac{-1}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv 3 \pmod {4}  \end{cases}$$

We also have the result we proved in Exercise (7.3)(11), that for a prime $p>3$,

$$ (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 11 \pmod {12}  \\ -1 & \text{ if } p \equiv 5 \text{ or } 7 \pmod {12}  \end{cases} $$

The following table summarises these results for an odd prime $p \pmod {12}$. The rows coloured grey are excluded as any integer with the corresponding congruence modulo 12 is not prime.

p mod 12	(-1/p)	(3/p)	(-1/p)(3/p)	p mod 6
1	1	1	1	1
2
3	-1
4
5	1	-1	-1	5
6
7	-1	-1	1	1
8
9	1
10
11	-1	1	-1	5

We can read off the desired result directly, for prime $p>3$,

$$ (\frac{-3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {6}  \\ -1 & \text{ if } p \equiv 5 \pmod {6}  \end{cases}$$

For the following exercises we require prime factors $p$ such that $x^2 \equiv -3 \pmod p$. By the above result we require primes that are congruent to 1 modulo 6. The first of these are 

$$ 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199 $$

(a) Trying factor 31 gives

$ 10819 = 31 \times 349 $.

Testing prime factors up to $\lfloor \sqrt{349} \rfloor = 18$ tells us 349 is prime.

(b) Trying prime factors 7, 73  and 109 gives

$ 55 699 = 7 \times 73 \times 109 $

(c) Trying prime factors 7, 97, and 193 gives

$ 131 047 = 7 \times 97 \times 193 $