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:

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

We visualized it as the middle column in this graphic.

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\) or \(p=11\)). It’s important to understood what is being asked before looking for patterns.

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\text{,}\) the sign of the following expression determines whether \(a\) is a QR.

\begin{equation*} a^{(p-1)/2}\equiv\pm 1\text{ (mod }p) \end{equation*}

We obtain \(+1\) if \(a\) is a QR, otherwise \(-1\text{.}\)

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\text{,}\) 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\text{,}\) the calculation is fairly simple:

\begin{equation*} 2^8=16^2\equiv (-1)^2 \equiv 1\text{ (mod }17)\text{,} \end{equation*}

as expected.

Can we confirm that \(3\) should not be on the list? Using Euler’s Criterion, we have

\begin{equation*} 3^8=9^4\equiv (-8)^4\equiv 8^4\equiv 16^3\equiv (-1)^3\equiv -1\text{ (mod }17)\text{,} \end{equation*}

which correctly shows \(3\) is not a quadratic residue.

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

Number Theory: In Context and Interactive

Search Results:

Section 16.5 Euler’s Criterion

Theorem 16.5.2. Euler’s Criterion.

Proof.

Example 16.5.3.

Example 16.5.4.