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

(\frac{2}{p})

was to look at numbers of the form

2 x

and factor out

2 .

So one might ask whether something like this calculation could work with general

a

and numbers like

a x

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

(\frac{a}{p})

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.

🔗

Historical remark 17.2.1. Gotthold Eisenstein.

Gotthold 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 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, a generalization of the Gaussian integers (see Exercise 14.4.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.

🔗

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

p = 13 .

🔗

Definition 17.2.2.

Fix an odd prime $p .$ Let $E$ be the set of positive even numbers less than $p .$ That is,

E = {2, 4, 6, \dots, p - 1} .

Next, given $a$ coprime to $p,$ let the set of multiples of $a$ by even numbers be denoted

a E = {2 a, 4 a, 6 a, \dots, (p - 1) a} .

Finally, find the remainder of each element of $a E$ modulo $p,$ as a nonnegative integer. The set of all such remainders we call $\overset{―}{a E};$ for convenience we may write $a e - k p = 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

a E .

(Also, here and elsewhere we are not considering the numbers in

\overset{―}{a E}

as elements of

Z_{p},

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 \overset{―}{a E} .$ Then as sets we have

{Remainder of (- 1)^{x} x ∣ x \in \overset{―}{a E}} = E .

🔗

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

E = {2, 4, 6, 8, 10} and \overset{―}{a E} = {6, 1, 7, 2, 8} .

The set in the claim is then

{(- 1)^{6} 6, (- 1)^{1} 1, (- 1)^{7} 7, (- 1)^{2} 2, (- 1)^{8} 8} \equiv {6, 10, 4, 2, 8} .

🔗

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 .

So a first step would be to multiply all the elements of

a E :

\prod_{e \in E} a e = a^{(p - 1) / 2} \prod_{e \in E} e .

🔗

Now let us reduce modulo

p;

recall the notation

r_{a, e}

for the remainder of

a e

in Definition 17.2.2. This gives a congruence:

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

🔗

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

we can write

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

🔗

Now substitute everything in the congruences. We obtain

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

🔗

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:

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

🔗

Example 17.2.5.

For instance, with $p = 11$ and $a = 3$ we can write $\prod_{e \in E} a e$ in two different ways, using first simple reduction and then Example 17.2.4:

6 \cdot 12 \cdot 18 \cdot 24 \cdot 30 \equiv 6 \cdot 1 \cdot 7 \cdot 2 \cdot 8

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 .

Checking, we see that $6 + 1 + 7 + 2 + 8$ is even. So by Theorem 16.5.2 $a$ should be a QR modulo $p,$ and $11 + 11 + 3 = 25 = 5^{2}$ so in this case it is easy to verify by hand that $(\frac{3}{11}) = 1 .$

🔗

More generally, we have the following fact.

🔗

Fact 17.2.6.

(\frac{a}{p}) = (- 1)^{\sum_{e \in E} r_{a, e}}

🔗

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 .

Indeed, we could have used Division Algorithm directly in defining them:

a e = p ⌊ \frac{a e}{p} ⌋ + r_{a, e}

🔗

So if we add up all the remainders, we get

\sum_{e \in E} r_{a, e} = \sum_{e \in E} a e - p \sum_{e \in E} ⌊ \frac{a e}{p} ⌋

🔗

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

1,

since they are the same modulo

2 .

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, \dots, p - 1};$ then

(\frac{a}{p}) = (- 1)^{\sum_{e \in E} ⌊ \frac{a e}{p} ⌋} .

🔗

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 [E.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,$ let's compute this exponent:

⌊ \frac{6}{11} ⌋ + ⌊ \frac{12}{11} ⌋ + ⌊ \frac{18}{11} ⌋ + ⌊ \frac{24}{11} ⌋ + ⌊ \frac{30}{11} ⌋ = 0 + 1 + 1 + 2 + 2 = 6 .

Once again this is even, so $3$ is confirmed to be a QR modulo $11 .$

🔗

Example 17.2.11.

Let's try to compute the exercise in Example 17.1.5 where $p = 17$ and $a = 45 \equiv 11 .$ Then we need to compute this exponent:

⌊ \frac{22}{17} ⌋ + ⌊ \frac{44}{17} ⌋ + ⌊ \frac{66}{17} ⌋ + ⌊ \frac{88}{17} ⌋ + ⌊ \frac{110}{17} ⌋ + ⌊ \frac{132}{17} ⌋ + ⌊ \frac{154}{17} ⌋ + ⌊ \frac{176}{17} ⌋

= 1 + 2 + 3 + 5 + 6 + 7 + 9 + 10 = 43 .

This is odd, so $45$ is not a QR modulo $17 .$

🔗

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.