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

• Let \(E\) be the set of even numbers less than \(p\). That is, \[E=\{2,4,6,\ldots,p-1\}\]
• Now, let's call the set of multiples of \(a\) by even numbers \(aE\); \[aE=\{2a,4a,6a,\ldots,(p-1)a\}\]
• The set of numbers \[\{(-1)^x x\mid x\in aE\}\] is the same as the set \(E\), considered as (least nonnegative) residue classes modulo \(p\). Why?
  • First, they are even: if \(x\) is even, then \((-1)^x x\) is just \(x\), while if \(x\) is odd, then \((-1)^x x\) is equivalent to \(p-x\), which (as the difference of two odds) is also even.
  • If any two such numbers were the same, then for some even numbers \(e\) and \(e'\) we have \[(-1)^{ae}ae\equiv (-1)^{ae'}ae'\] and since \(gcd(a,p)=1\) we can remove the \(a\) and get that \[e\equiv \pm e'\]
  • If \(e\) and \(e'\) are different then \(e\equiv -e'\) and \(e+e'\equiv 0\); but \(e+e'=2p\) is not possible since they are smaller than \(p\), and \(e+e'=p\) is not possible since \(p\) is odd.
  • Thus \(e=e'\).

Now let's try to get something like in Euler's criterion.

• We would need to arrive at \(a^{(p-1)/2}\). Notice that the exponent is exactly the number of elements in \(E\).
• So we could look at \[\prod_{e\in E}ae=a^{(p-1)/2}\prod_{e\in E}e\]
• So let's give a name to the least positive residues modulo \(p\) of each \(ae\) for \(e \in E\); call them \(r_e\). So the previous statement, modulo \(p\), is \[\prod_{e\in E}r_e\equiv a^{(p-1)/2}\prod_{e\in E}e\]
• Then, using the fact we proved above about \((-1)^x\) and the set \(E\), and getting the power of \((-1)\) in question, we can write \[\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\]
• Now we substitute and move minus signs. This gets us that \[\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\] which means, since dividing and multiplying by powers of \((-1)\) is the same thing, \[a^{(p-1)/2}\equiv (-1)^{\sum_{e\in E}r_e}\; .\]
• Using Euler's criterion gives us \[\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}r_e}\; .\]

So we have reduced evaluating the Legendre symbol (and hence deciding whether things have square roots modulo \(p\)) to the parity of a certain sum; hopefully that's an improvement on taking powers.

Of course, it's still somewhat unwieldy, so there is a final simplification.

• Where do these \(r_e\) come from anyway? Well, for \(e\in E\), they are the least positive residues, and that is precisely what we get from the division algorithm: \[ae=p\left\lfloor\frac{ae}{p}\right\rfloor+r_e\]
• So if we add them all up, we get \[\sum_{e\in E}r_e=\sum_{e\in E}ae-p\sum_{e\in E}\left\lfloor\frac{ae}{p}\right\rfloor\]
• But we only care about the parity of this sum!
  • This is actually very often true in algebra and number theory.
  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\).

Thus we get the final form of the criterion. (The name of the criterion is long to avoid confusion with another famous criterion Eisenstein came up with.)

This very abstruse-seeming criterion will actually be the key to proving Gauss' theorem. Next, we'll see how to use it “hands-on” to calculate some Legendre symbols somewhat more easily than above.