Theorem 16.7.1. When Two is a Quadratic Residue.
The quadratic residue of two modulo an odd prime \(p\) is as follows.
- \(\left(\frac{2}{p}\right)=1\) if \(p\equiv \pm 1\) (mod \(8\))
- \(\left(\frac{2}{p}\right)=-1\) if \(p\equiv \pm 3\) (mod \(8\))
Section 16.7 Our First Full Computation
We will now complete our investigations begun in Subsection 16.3.2 by calculating \(\left(\frac{2}{p}\right)\) using Euler’s Criterion. (There are many proofs of the following fact; a nice one using only the existence of a primitive root is [E.7.16].)
Proof.
We will show this by writing \((p-1)!\) in two different ways below in Proof 16.7.1.
Example 16.7.2.
It is easiest to approach the proof first with an example. We will take \(p=11\text{.}\)
We can write
\begin{equation*}
(11-1)!=10!=1(2)(3)(4)(5)(6)(7)(8)(9)(10)
\end{equation*}
\begin{equation*}
=(2\cdot 4\cdot 6\cdot 8\cdot 10)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)
\end{equation*}
\begin{equation*}
=2^5 \cdot (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\text{.}
\end{equation*}
Notice that \(1,3,5\) repeat; these are all the odd numbers less than or equal to \(\frac{11-1}{2}=5\text{.}\)
Now we will try to create \(10!\) again from the numbers on the right after we have factored out \(2\text{.}\) In this case, the only ones repeated are \(1,3,5\text{,}\) so we are almost there.
But observe that \(-1,-3,-5\equiv 10,8,6\text{,}\) which are exactly the missing pieces of \(10!\text{.}\) So I will factor out \(-1\) from those three, thus:
\begin{equation*}
10!=2^5 \cdot (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)
\end{equation*}
\begin{equation*}
\equiv 2^5 \cdot (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (-1)^3\cdot (-1\cdot -3\cdot -5)\cdot (7\cdot 9)
\end{equation*}
\begin{equation*}
\equiv 2^5 \cdot (-1)^3 \cdot (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (10\cdot 8\cdot 6)(7\cdot 9)\equiv (-1)^3 \cdot 2^5 \cdot (10!)\text{ (mod }11)\text{.}
\end{equation*}
Finally, cancel \(10!\) from the first and last element of the preceding chain of congruences, and we get
\begin{equation*}
1\equiv 2^5 (-1)^3 \Longrightarrow 2^{(11-1)/2}\equiv 2^5\equiv (-1)^3\equiv -1\text{ (mod }11)
\end{equation*}
and so 2 is not a QR of 11.
Proof of Theorem 16.7.1.
Proving the general case basically follows the procedure in the previous example to its natural conclusion; there was nothing special in the above argument about \(p=11\text{.}\)
After writing \((p-1)!\) and factoring out \(2^{(p-1)/2}\text{,}\) the “repeated” numbers will be the odd numbers between 1 and \((p-1)/2\text{.}\) Clearly the only “missing” numbers are even ones between \((p-1)/2\) and \(p\text{,}\) which are just congruent to the negatives of the “repeated” odd numbers, so the same argument as above with \((p-1)!\) will work.
It remains to check when we have a QR and when we do not.
- If \(p\equiv 3\) (mod \(4\)), like \(p=11\text{,}\) then \((p-1)/2\) is odd so there will be\begin{equation*} \left(\frac{p-1}{2}-1\right)\frac{1}{2}+1=\frac{p+1}{4} \end{equation*}repeated factors, as \(1,3,5\) above.
- If \(p\equiv 1\) (mod \(4\)) (like \(p=17\)), on the other hand, then \((p-1)/2\) is even and there are exactly\begin{equation*} \left(\frac{p-1}{2}\right)\frac{1}{2}=\frac{p-1}{4} \end{equation*}repeated factors (in that case, \(1,3,5,7\)).
In either case, whether the number of repeated factors (\((p+1)/4\) or \((p-1)/4\text{,}\) respectively) is even or odd determines whether 2 is a quadratic residue.
Now we simply confirm the formula given in Theorem 16.7.1 in all four possible cases:
- If \(p\equiv 1\) (mod \(4\)) and \(\frac{p-1}{4}\) is even, \(\left(\frac{2}{p}\right)=1\text{.}\) These conditions imply \(p\equiv 1\) (mod \(8\)), so 2 is a QR when \(p\equiv 1\) (mod \(8\)).
- If \(p\equiv 1\) (mod \(4\)) and \(\frac{p-1}{4}\) is odd, \(\left(\frac{2}{p}\right)=-1\text{.}\) These conditions imply \(p\equiv 5\) (mod \(8\)), so 2 is not a QR when \(p\equiv 5\) (mod \(8\)).
- If \(p\equiv 3\) (mod \(4\)) and \(\frac{p+1}{4}\) is even, \(\left(\frac{2}{p}\right)=1\text{.}\) These conditions imply \(p\equiv 7\) (mod \(8\)), so 2 is a QR when \(p\equiv 7\) (mod \(8\)).
- If \(p\equiv 3\) (mod \(4\)) and \(\frac{p+1}{4}\) is odd, \(\left(\frac{2}{p}\right)=-1\text{.}\) These conditions imply \(p\equiv 3\) (mod \(8\)), so 2 is not a QR when \(p\equiv 3\) (mod \(8\)).
The following Sage cell shows off Theorem 16.7.1, incidentally confirming a computation in Example 16.5.4.
In the next chapter, we will vastly expand our repertoire of Legendre symbols, and see many applications.
