##
Section 17.2 Another Criterion

Now, we might want to do something more general than just try to compute Legendre symbols one by one. Notice that what we did in using the

Euler’s Criterion to find

\(\left(\frac{2}{p}\right)\) was to look at numbers of the form

\(2x\) and factor out

\(2\text{.}\) So one might ask whether something like this

*calculation* could work with general

\(a\) and numbers like

\(ax\) to find a better

*theoretical* result.

It turns out that this is true. We are going to follow the steps of Gauss’ protege Gotthold Eisenstein here to find a way to evaluate

\(\left(\frac{a}{p}\right)\) for

\(p\) an odd prime and

\(\gcd(a,p)=1\text{.}\) It will be slow, and we won’t see the payoff until we prove

Theorem 17.4.1, but it

*will* give us good practice in thinking about the numbers themselves.

###
Subsection 17.2.1 Laying the foundation

First, let’s introduce a new set and look at a couple of properties. I *strongly* advise following along with a prime like \(p=11\) or \(p=13\text{.}\)

####
Definition 17.2.2.

Fix an odd prime \(p\text{.}\) Let \(E\) be the set of positive even numbers less than \(p\text{.}\) That is,

\begin{equation*}
E=\{2,4,6,\ldots,p-1\}\text{.}
\end{equation*}

Next, given \(a\) coprime to \(p\text{,}\) let the set of multiples of \(a\) by even numbers be denoted

\begin{equation*}
aE=\{2a,4a,6a,\ldots,(p-1)a\}\text{.}
\end{equation*}

Finally, find the *remainder* of each element of \(aE\) modulo \(p\text{,}\) as a nonnegative integer. The set of all such remainders we call \(\overline{aE}\text{;}\) for convenience we may write \(ae-kp=r_{a,e}\) for the remainder (and quotient \(k\)).

The construction of this should ring bells, because just as in

Theorem 16.7.1 and

Lemma 13.3.3 we could potentially factor out

\((p-1)/2\) factors of

\(a\) from a product of the elements of

\(aE\text{.}\) (Also, here and elsewhere we are not considering the numbers in

\(\overline{aE}\) as elements of

\(\mathbb{Z}_p\text{,}\) but as integers.)

####
Claim 17.2.3.

Consider the set of (least nonnegative) remainders modulo \(p\) of numbers of the form \((-1)^x x\) for \(x\in \overline{aE}\text{.}\) Then as sets we have

\begin{equation*}
\{\text{ Remainder of }(-1)^x x\mid x\in \overline{aE}\}=E\text{.}
\end{equation*}

#### Proof.

First, we claim both sets only contain even numbers. Recall that everything in \(\overline{aE}\) is less than \(p\text{.}\)

If \(x\) is even, then \((-1)^x x\) is just \(x\text{,}\) which will then be the remainder.

If \(x\) is odd, then \((-1)^x x = -x\) has remainder \(p-x\text{,}\) which (as the difference of two odds) is also even.

It remains to show the elements of the set in question are all different.

Suppose any two such numbers were the same; then for some even numbers \(e\) and \(e'\text{,}\) and quotients \(k\) and \(k'\text{,}\) we have

\begin{equation*}
(-1)^{ae-kp}(ae-kp)\equiv (-1)^{ae'-k'p}(ae'-k'p)\text{ (mod }p)\text{.}
\end{equation*}

We can reduce this further by ignoring multiples of \(p\text{,}\) and even further by observing that \(\gcd(a,p)=1\) so we can cancel \(a\) from the remaining congruence. Then

\begin{equation*}
e\equiv \pm e'\text{.}
\end{equation*}

If \(e\) and \(e'\) are different then \(e\not\equiv e'\text{,}\) so the only option would be \(e\equiv -e'\text{.}\) This directly yields \(e+e'\equiv 0\text{.}\) But numbers in \(E\) are positive and less than \(p\text{,}\) so \(0\lt e+e'\lt 2p\text{.}\) Since \(p\) is odd we also cannot have the sum of two evens \(e+e'=p\text{,}\) so the only remaining choice is that \(e=e'\text{.}\)

####
Example 17.2.4.

For instance, with \(p=11\) and \(a=3\) we get

\begin{equation*}
E=\{2,4,6,8,10\}\text{ and }\overline{aE}=\{6,1,7,2,8\}\text{.}
\end{equation*}

The set in the claim is then

\begin{equation*}
\{(-1)^{6} 6,(-1)^{1} 1,(-1)^{7} 7,(-1)^{2}2,(-1)^8 8\}\equiv \{6,10,4,2,8\}\text{.}
\end{equation*}

###
Subsection 17.2.2 Getting the new criterion

Now we will try to use this set to arrive at something similar to

Euler’s Criterion. Our goal would be to use it (since we know it corresponds to Legendre symbols), but with something different and hopefully easier to compute. Still, we would need to arrive at

\(a^{(p-1)/2}\) in the end, so let’s follow some steps that might lead us in that direction.

As mentioned above, the most crucial thing to notice is that the desired exponent \((p-1)/2\) is exactly the number of elements in \(E\text{.}\) So a first step would be to *multiply* all the elements of \(aE\text{:}\)

\begin{equation*}
\prod_{e\in E}ae=a^{(p-1)/2}\prod_{e\in E}e\text{.}
\end{equation*}

Now let us reduce modulo

\(p\text{;}\) recall the notation

\(r_{a,e}\) for the remainder of

\(ae\) in

Definition 17.2.2. This gives a

*congruence*:

\begin{equation*}
\prod_{e\in E}r_{a,e}\equiv a^{(p-1)/2}\prod_{e\in E}e\text{.}
\end{equation*}

Focus temporarily just on the product of

\(e\)s on the right hand side. Using

Claim 17.2.3 and factoring out all the powers of

\((-1)\text{,}\) we can write

\begin{equation*}
\prod_{e\in E}e\equiv\prod_{e\in E} (-1)^{r_{a,e}}r_{a,e}\equiv (-1)^{\sum_{e\in E}r_{a,e}}\prod_{e\in E}r_{a,e}\text{.}
\end{equation*}

Now substitute everything in the congruences. We obtain

\begin{equation*}
\prod_{e\in E}r_{a,e}\equiv a^{(p-1)/2}\prod_{e\in E}e\equiv a^{(p-1)/2}(-1)^{\sum_{e\in E}r_{a,e}}\prod_{e\in E}r_{a,e}\text{.}
\end{equation*}

Now if we cancel the product of the remainders and note that dividing and multiplying by powers of

\((-1)\) is the same thing, we can connect to

Theorem 16.5.2:

\begin{equation*}
a^{(p-1)/2}\equiv (-1)^{\sum_{e\in E}r_{a,e}}\text{.}
\end{equation*}

####
Example 17.2.5.

For instance, with

\(p=11\) and

\(a=3\) we can write

\(\prod_{e\in E}ae\) in two different ways, using first simple reduction and then

Example 17.2.4:

\begin{equation*}
6\cdot 12\cdot 18\cdot 24\cdot 30\equiv 6\cdot 1\cdot 7\cdot 2\cdot 8
\end{equation*}

\begin{equation*}
6\cdot 12\cdot 18\cdot 24\cdot 30\equiv 3^5\cdot 2\cdot 4\cdot 6\cdot 8\cdot 10 \equiv 3^{5}(-1)^{6+1+7+2+8}\cdot 6\cdot 1\cdot 7\cdot 2\cdot 8\text{.}
\end{equation*}

Checking, we see that

\(6+1+7+2+8\) is even. So by

Theorem 16.5.2 \(a\) should be a QR modulo

\(p\text{,}\) and

\(11+11+3=25=5^2\) so in this case it is easy to verify by hand that

\(\left(\frac{3}{11}\right)=1\text{.}\)
More generally, we have the following fact.

####
Fact 17.2.6.

\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}r_{a,e}}
\end{equation*}

#### Proof.

What have we done? We have reduced evaluating the Legendre symbol (and hence deciding whether things have square roots modulo \(p\)) to calculating the *parity* of a certain sum. Given that in the previous chapter we had to calculate fairly large powers of modular integers, this could be an important improvement.

###
Subsection 17.2.3 The final form

Fact 17.2.6 is still somewhat unwieldy, so there is a final simplification.

Recall that these

\(r_{a,e}\) come from remainders of

\(e\in E\text{.}\) Indeed, we could have used

Division Algorithm directly in defining them:

\begin{equation*}
ae=p\left\lfloor\frac{ae}{p}\right\rfloor+r_{a,e}
\end{equation*}

So if we add up all the remainders, we get

\begin{equation*}
\sum_{e\in E}r_{a,e}=\sum_{e\in E}ae-p\sum_{e\in E}\left\lfloor\frac{ae}{p}\right\rfloor
\end{equation*}

But we only care about the *parity* of this sum! So we can remove the whole piece with \(e\) in it, as that’s all even, and we can replace the \(-p\) by \(1\text{,}\) since they are the same modulo \(2\text{.}\) This leaves the following much simpler criterion.

####
Theorem 17.2.8. Eisenstein’s Criterion for the Legendre Symbol.

Let \(p\) and \(a\) be as throughout, and \(E=\{2,4,6,\ldots,p-1\}\text{;}\) then

\begin{equation*}
\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}\left\lfloor\frac{ae}{p}\right\rfloor}\text{.}
\end{equation*}

####
Example 17.2.10.

To continue

Example 17.2.5 where

\(p=11\) and

\(a=3\text{,}\) let’s compute this exponent:

\begin{equation*}
\left\lfloor \frac{6}{11}\right\rfloor+\left\lfloor \frac{12}{11}\right\rfloor+\left\lfloor \frac{18}{11}\right\rfloor+\left\lfloor \frac{24}{11}\right\rfloor+\left\lfloor \frac{30}{11}\right\rfloor=0+1+1+2+2=6\text{.}
\end{equation*}

Once again this is even, so \(3\) is confirmed to be a QR modulo \(11\text{.}\)

####
Example 17.2.11.

Let’s try to compute the exercise in

Example 17.1.5 where

\(p=17\) and

\(a=45\equiv 11\text{.}\) Then we need to compute this exponent:

\begin{equation*}
\left\lfloor \frac{22}{17}\right\rfloor+\left\lfloor \frac{44}{17}\right\rfloor+\left\lfloor \frac{66}{17}\right\rfloor+\left\lfloor \frac{88}{17}\right\rfloor+\left\lfloor \frac{110}{17}\right\rfloor+\left\lfloor \frac{132}{17}\right\rfloor +\left\lfloor \frac{154}{17}\right\rfloor +\left\lfloor \frac{176}{17}\right\rfloor
\end{equation*}

\begin{equation*}
=1+2+3+5+6+7+9+10=43\text{.}
\end{equation*}

This is odd, so \(45\) is not a QR modulo \(17\text{.}\)

This very abstruse-seeming criterion will actually be the key to proving the soon-to-come

Theorem 17.4.1. See Laubenbacher and Pengelley’s article

[E.7.8] for an excellent exposition, which I have expanded on significantly above.

`www-groups.dcs.st-and.ac.uk/history/Biographies/Eisenstein.html`

`mathworld.wolfram.com/EisensteinInteger.html`