NTIC Our First Full Computation

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

🔗

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$ )

🔗

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

xxxxxxxxxx
 
@interact
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)))

🔗

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