Section 16.7 Our First Full Computation
We will now complete our investigations begun in Subsection 16.3.2 by calculatingTheorem 16.7.1. When Two is a Quadratic Residue.
The quadratic residue of two modulo an odd prime
if (mod ) if (mod )
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
We can write
Notice that
Now we will try to create
But observe that
Finally, cancel
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\)).
xxxxxxxxxx
def _(p = (17,prime_range(3,100))):
l = legendre_symbol(2,p)
r = p%8
pretty_print(html(r"The prime $%s\equiv %s\text{ (mod }8)$ and $\left(\frac{2}{%s}\right)=%s$."%(p,r,p,l)))