NTIC Another Criterion

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.

🔗

Remark 17.2.1.

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; unfortunately, their mathematics is mostly outside the bounds of this text.

🔗

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 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 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}\cdot 6\cdot 1\cdot 7\cdot 2\cdot 8 \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.

🔗

More generally, we have the following fact.

🔗

Fact 17.2.6.

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

🔗

Proof.

Use Euler's Criterion and the above steps.

🔗

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.

🔗

Remark 17.2.7.

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

🔗

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*}$

🔗

Remark 17.2.9.

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 [C.7.4], which won the Lester R. Ford award, on whether Theodor Schönemann deserves the credit for that criterion.)

🔗

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 [C.7.8] for an excellent exposition, which I have expanded on significantly above.