(i) Prove that for prime $p > 3$ we have
$$ (\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} $$
(ii) Show that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$.
(iii) Factorise the following integers:
(a) $62^2 -3 = 3841$
(b) $104^2 -3 = 10813$
(c) $200^2 - 3 = 39997$
(d) $364^2 -3 = 132493$
(e) $568^2 -3 = 322621$
(i) We start with Gauss's Lemma that
$$ (\frac{3}{p}) = (-1)^g $$
where $g$ is the number of residues of $p$ greater than $\frac{p-1}{2}$ in the set $\{3\cdot 1, \;3\cdot 2, \;3 \cdot 3, \;\ldots , \; 3 \cdot \frac{p-1}{2}\}$.
The value of $g$ is the number of integers from the set $1,2, 3, \ldots, p-1$ which map to a value greater than $\frac{p-1}{2}$ up to and including $p-1$. This value of $g$ is
$$ g = \lfloor \frac{p-1}{3} \rfloor - \lfloor \frac{p-1}{2 \cdot 3} \rfloor $$
We write odd prime $p$ as $p=12k + t$ for some integer $k$ and where $t$ is only one of $1, 5, 7, 11$. Other values of $t$ contradict $p$ being prime. We consider each case for values of $t$.
For $p=12k +1$ we have
$$ \begin{align} g & = \lfloor \frac{12k+1-1}{3} \rfloor - \lfloor \frac{12k+1-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k \rfloor - \lfloor 2k \rfloor \\ \\ & = 2k \end{align} $$
Because $g$ is even, we have
$$ (\frac{3}{p}) = (-1)^g = 1 $$
For $p=12k +5$ we have
$$ \begin{align} g & = \lfloor \frac{12k+5-1}{3} \rfloor - \lfloor \frac{12k+5-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{4}{3} \rfloor - \lfloor 2k + \frac{4}{6} \rfloor \\ \\ & = (4k+1) - (2k) \\ \\ &= 2k+1 \end{align} $$
Because $g$ is odd, we have
$$ (\frac{3}{p}) = (-1)^g = -1 $$
For $p=12k +7$ we have
$$ \begin{align} g & = \lfloor \frac{12k+7-1}{3} \rfloor - \lfloor \frac{12k+7-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{6}{3} \rfloor - \lfloor 2k + \frac{6}{6} \rfloor \\ \\ & = (4k+2) - (2k+1) \\ \\ &= 2k+1 \end{align} $$
Because $g$ is odd, we have
$$ (\frac{3}{p}) = (-1)^g = -1 $$
For $p=12k +11$ we have
$$ \begin{align} g & = \lfloor \frac{12k+11-1}{3} \rfloor - \lfloor \frac{12k+11-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{10}{3} \rfloor - \lfloor 2k + \frac{10}{6} \rfloor \\ \\ & = (4k+3) - (2k+1) \\ \\ &= 2k+2 = 2(k+1) \end{align} $$
Because $g$ is even, we have
$$ (\frac{3}{p}) = (-1)^g = 1 $$
We have consider all the cases for $p$ and they all support the desired conclusion that for odd prime $p$
$$ (\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} $$
(ii) To show that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$, we need to show both
- if $p \equiv 1,11 \pmod {12}$ then 3 is a quadratic residue of $p$
- if $3$ is a quadratic residue of $p$ then $p \equiv 1,11 \pmod {12}$
($\impliedby$)
The result we proved in part (i) immediately gives us that if $p \equiv 1,11 \pmod {12}$ then 3 is a quadratic residue of $p$, because by Euler's Criterion $(\frac{3}{p})=1$ means 3 is a quadratic residue of $p$.
($\implies$)
We will prove the logically equivalent contrapositive: if $p \not \equiv 1, 11 \pmod {12}$ then $3$ is not a quadratic residue of $p$.
If $p \not \equiv 1, 11 \pmod {12}$ then it must be the case that $p \not \equiv 5, 7 \pmod {12}$ because any other congruent values for $p$ would contradict $p$ being prime. The result from (i) tells us that $(\frac{3}{p})=-1$, and so by Euler's Criterion 3 is not a quadratic residue of $p$.
We have proved the contrapositive, which is equivalent to $3$ is a quadratic residue of $p$ then $p \equiv 1,11 \pmod {12}$.
By proving both directions of the bi-conditional statement, we have proven the statement that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$.
(iii) The factorisation exercises require a list of the first odd primes which are congruent to 1 or 11 modulo 12. These are
$$ 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, 227, 229, 239, 241 $$
(a) $62^2 \equiv 3 \pmod p$ means $p$ is congruent to 1 or 11 modulo 12 by the result proved above in part (i). Such a $p$ is a factor of $62^2-3$ because $62^2 -3 \equiv 0 \pmod p$.
Trying factor 23 gives
$ 3841 = 23 \times 167 $
(b) Trying factor 11 gives
$ 10813 = 11 \times 983 $
Trying factors up to $\lfloor \sqrt{983} \rfloor = 31$ shows 983 is prime.
(c) Trying factors 23, 37 and 47 gives
$39997 = 23 \times 37 \times 47$
(d) Trying factor 47 gives
$ 132493 = 47 \times 2819$
Trying factors up to $\lfloor \sqrt{2819} \rfloor = 53$ shows 2819 is prime.
(e) Trying factors 13, 23 and 83 gives.
$ 322621 = 13^2 \times 23 \times 83$