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 like \(2x\). 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 Eisenstein here to find a way to evaluate \(\left(\frac{a}{p}\right)\) for \(p\) an odd prime and \(\gcd(a,p)=1\). 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.
Eisenstein was yet another brilliant young mathematician who came out of nowhere but died young because he couldn't find a job which could help his chronic illness. (I say “yet another” because this is similar to the story of Abel (after whom Abelian groups are named), and quite likely would have been the story of Galois if he hadn't been killed in a duel first).
First, let's introduce a new set and look at a couple properties. I strongly advise following along with a prime like \(p=11\) or \(p=13\).
Fix an odd prime \(p\). Let \(E\) be the set of even numbers less than \(p\). That is, \begin{equation*}E=\{2,4,6,\ldots,p-1\}\end{equation*} Then call the set of multiples of \(a\) by even numbers \(aE\) (reduced modulo \(p\)) so that \begin{equation*}aE=\{2a,4a,6a,\ldots,(p-1)a\}\end{equation*}
The set of numbers \begin{equation*}\{(-1)^x x\mid x\in aE\}\end{equation*} is the same as the set \(E\), considered as (least nonnegative) residue classes modulo \(p\).
For instance, with \(p=11\) and \(a=3\) we get \(E=\{2,4,6,8,10\}\) and the set in the claim as \begin{equation*}\{(-1)^{6} 6,(-1)^{1} 1,(-1)^{7} 7,(-1)^{2}2,(-1)^8 8\}\equiv \{6,10,4,2,8\}\end{equation*}
Now we will try to use this set to arrive at something similar to Euler's criterion. Our goal would be to actually have that in it, but with something different to compute, so we would need to arrive at \(a^{(p-1)/2}\) in the end. Let's follow some steps that might lead us in that direction.
Crucially, notice first that the exponent is exactly the number of elements in \(E\). So to get this, we could multiply all of them: \begin{equation*}\prod_{e\in E}ae=a^{(p-1)/2}\prod_{e\in E}e\end{equation*}
With that in mind, let's give a name to the least positive residues modulo \(p\) of each \(ae\) for \(e \in E\); call them \(r_e\). Then the previous statement, modulo \(p\), is \begin{equation*}\prod_{e\in E}r_e\equiv a^{(p-1)/2}\prod_{e\in E}e\end{equation*} (Note the change from \(=\) to \(\equiv\).)
If we focus temporarily just on the product of \(e\)s, then using Claim 17.2.3 and adding all the powers of \((-1)\) in question, we can write \begin{equation*}\prod_{e\in E}e\equiv\prod_{e\in E} (-1)^{r_e}r_e\equiv (-1)^{\sum_{e\in E}r_e}\prod_{e\in E}r_e\end{equation*}
Now we substitute everything from the previous points together and move minus signs via multiplication. This gets us that \begin{equation*}\prod_{e\in E}r_e\equiv a^{(p-1)/2}\prod_{e\in E}e\equiv a^{(p-1)/2}(-1)^{\sum_{e\in E}r_e}\prod_{e\in E}r_e\end{equation*} which means, since dividing and multiplying by powers of \((-1)\) is the same thing, \begin{equation*}a^{(p-1)/2}\equiv (-1)^{\sum_{e\in E}r_e}\; .\end{equation*}
For instance, with \(p=11\) and \(a=3\) we get \begin{equation*}6\cdot 12\cdot 18\cdot 24\cdot 30\equiv 6\cdot 1\cdot 7\cdot 2\cdot 8\equiv 2^{5}(-1)^{6+1+7+2+8}6\cdot 1\cdot 7\cdot 2\cdot 8\end{equation*} Checking, we see that \(6+1+7+2+8\) is even. So by Euler's criterion \(a\) should be a QR modulo \(p\), and \(11+11+3=25=5^2\) so in this case it is.
More generally, we have the following resulting fact.
\begin{equation*}\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}r_e}\end{equation*}
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. Hopefully that's an improvement on taking powers.
Transforming such computations to a simple parity (or other) check is very common in algebra and number theory.
Of course, Fact 17.2.6 is still somewhat unwieldy, so there is a final simplification.
First, where do these \(r_e\) come from anyway? Well, for \(e\in E\), they are the least positive residues, and that means they are precisely what we get from the Division Algorithm: \begin{equation*}ae=p\left\lfloor\frac{ae}{p}\right\rfloor+r_e\end{equation*} So if we add them all up, we get \begin{equation*}\sum_{e\in E}r_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\), since they are the same modulo \(2\).
\begin{equation*}\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}\left\lfloor\frac{ae}{p}\right\rfloor}\; .\end{equation*}
The name of the criterion is long to avoid confusion with another famous criterion Eisenstein came up with. (See David Cox's excellent 2011 Monthly article [C.6.4], which won the Lester R. Ford award, on whether Theodor Schönemann deserves the credit for that criterion too.)
To continue the example with \(p=11\) and \(a=3\), 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{20}{11}\right\rfloor=0+1+1+2+2=6\end{equation*}Once again, this is even so \(3\) is confirmed to be a QR modulo \(11\).
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 [C.6.8] for an excellent exposition which is elaborated on significantly above.
