NTIC Euler's Criterion

Section 16.5 Euler's Criterion

As it happens, Fact 16.4.5 is a terrible way to actually find quadratic residues for a given

p

in general, since it involves finding a primitive root and listing lots of powers. We need both theory and practice.

🔗

There is a much easier way. First recall our observation in Theorem 12.3.2:

a^{(p - 1) / 2} \equiv \pm 1 for all a not divisible by p .

🔗

We visualized it as the middle column in this graphic.

Colored table of powers modulo $n=13$ — 🔗
Figure 16.5.1. Colored table of powers modulo $n = 13$

🔗

But as so often in mathematics, solving one question leads to another; after all, Theorem 12.3.2 didn't say when we got plus or minus 1, just that these are the only possibilities. Observe carefully above which rows start with the colors corresponding to squares (the column labeled 2), comparing them to whether the middle column is black or white.

🔗

Don't go on until you have tried this (interactively below, or even by hand with

p = 7

p = 11

). It's important to understood what is being asked before looking for patterns.

xxxxxxxxxx
 
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
@interact
def power_table_plot(p=(13,prime_range(50)[2:])):
    mycmap = plt.get_cmap('gist_earth',p-1)
    myloc = IndexLocator(floor(p/5),.5)
    myform = FuncFormatter(lambda x,y: int(x+1))
    cbaropts = {  'ticks':myloc, 'drawedges':True, 'boundaries':srange(.5,p+.5,1)}
    P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p+1)]), cmap=mycmap,colorbar=True, colorbar_options=cbaropts, ticks=[myloc,myloc], tick_formatter=[None,myform])    
    show(P,figsize=6)

🔗

Hopefully you did notice a pattern. Let's formalize it as follows.

🔗

Theorem 16.5.2. Euler's Criterion.

If $p$ is an odd prime, then for all integers $a$ not a multiple of $p,$ the sign of the following expression determines whether $a$ is a QR.

a^{(p - 1) / 2} \equiv \pm 1 (mod p)

We obtain $+ 1$ if $a$ is a QR, otherwise $- 1 .$

🔗

Proof.

Let $g$ be a primitive root of $p\text{,}$ so that $a\equiv g^i$ for some $i\text{.}$ Then if we let $h=g^{(p-1)/2}\text{,}$ Fermat's Little Theorem shows that

\begin{equation*} h^2=g^{p-1}\equiv 1\text{ (mod }p)\text{.} \end{equation*}

Since $g$ is a primitive root, $h\equiv 1$ is impossible, so $h\equiv -1\text{.}$ But then

\begin{equation*} a^{(p-1)/2}\equiv \left(g^i\right)^{(p-1)/2}\equiv \left(g^{(p-1)/2}\right)^i\equiv h^i \equiv (-1)^i\text{.} \end{equation*}

This is $+1$ when $i$ is even and $-1$ when $i$ is odd. Finally, according to Fact 16.4.5, this is precisely when $a$ is a quadratic residue and nonresidue, respectively.

🔗

Example 16.5.3.

This immediately gives the result in Fact 16.1.2 that $- 1$ has a square root modulo an odd prime $p$ precisely when $p \equiv 1$ (mod $4$ ), because $(- 1)^{(p - 1) / 2} = + 1$ precisely when $(p - 1) / 2$ is even, or $p \equiv 1$ (mod $4$ ). That is much easier than our previous ad-hoc way of doing it!

🔗

Example 16.5.4.

Let's use this to confirm, for $p = 17,$ two of the values implicit in the list we obtained in Sage note 16.3.3.

First, that list included $2$ as a QR. Since $(p - 1) / 2 = 8,$ the calculation is fairly simple:

2^{8} = 16^{2} \equiv (- 1)^{2} \equiv 1 (mod 17),

as expected.

Can we confirm that $3$ should not be on the list? Using Euler's Criterion, we have

3^{8} = 9^{4} \equiv (- 8)^{4} \equiv 8^{4} \equiv 16^{3} \equiv (- 1)^{3} \equiv - 1 (mod 17),

which correctly shows $3$ is not a quadratic residue.

🔗

We will now greatly amplify the power of our work thus far.