Skip to main content

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].)

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.

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 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.

In the next chapter, we will vastly expand our repertoire of Legendre symbols, and see many applications.