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.

was yet another brilliant young mathematician who came out of nowhere but died young because he couldn’t find a job which could help him financially enough to deal with his chronic illness. His work in several areas of algebra and function theory is still considered forward-looking. Of particular interest for this text is the Eisenstein integers^{ 2 }

I say “yet another” because this is similar to the story of Niels Abel (after whom Abelian groups are named), and quite likely would have been the story of Évariste Galois if he hadn’t been killed in a duel first; unfortunately, their mathematics is mostly outside the bounds of this text.

Subsection17.2.1Laying 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{.}\)

Definition17.2.2.

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

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

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

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

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{.}\)

Example17.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*}

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{:}\)

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

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:

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{.}\)

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.

Remark17.2.7.

Transforming such computations to a simple parity (or other) check is very common in algebra and number theory.

Subsection17.2.3The 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:

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.

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

The name of the criterion is long to avoid confusion with another famous criterion that Eisenstein discovered. (See David Cox’s excellent 2011 Monthly article [E.7.4], which won the Lester R. Ford award, on whether Theodor Schönemann deserves the credit for that criterion.)

Example17.2.10.

To continue Example 17.2.5 where \(p=11\) and \(a=3\text{,}\) let’s compute this exponent:

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.