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