Section16.6The Legendre Symbol
We now introduce a new notation for this entire discussion. Why? Think on this; Gauss revolutionized number theory, and much of what made it possible (and accessible to others) was the notion of congruence, along with the symbol \(\equiv\).
We alluded to a great innovation of Legendre's earlier, and it is likewise a concept and symbol. Earlier in his research into these questions, he discovered that certain powers were always either \(\pm 1\), omitting multiples of what we would today call the modulus. Some of what he found was essentially the criterion of Euler's we just proved.
Subsection16.6.1Introducing the Legendre Symbol
What of the plus or minus 1? As Weintraub says in his article on this, if one had a symbol for it, it becomes “more than a notational convenience... Legendre reifies this concept, and makes it into an object of independent study.”
In our modern terms, he takes advantage of the fact that \(a=g^i\) is an even power exactly when \(a\) is a QR, and \((-1)^i=1\) precisely when \(i\) is even (and hence precisely when \(a\) is a QR). This is the so-called Legendre symbol. (However, he did not use the term QR, just the symbol.)
Example16.6.2
So e.g. \(\left(\frac{-1}{p}\right)=1\) for \(p\) prime if and only if \(p=2\) or \(p\equiv 1\) mod (4).
The command in Sage is pretty straightforward.
A brief note is in order regarding the special status of zero. On the one hand, this recognizes the special case that \(0^2=0\), while \(1=1^2=(-1)^2\) (and everything else) usually have two square roots modulo a prime. On the other hand, this also conveniently ignores the only integer from \(0\) to \(p-1\) which is not in \(U_p\), so that in fact you can think of \(x\to \left(\frac{x}{p}\right)\) to be a function from \(U_p\) to \(\{1,-1\}\) of the kind we call a group homomorphism. (Indeed, it gets us from a cyclic group of order \(p-1\) to a cyclic group of order \(2\), with "kernel" a cyclic group of order \((p-1)/2\).)
Subsection16.6.2Primitive Roots and Quadratic Residues
Let's use our usual example to visualize the tension and connection between primitive roots and quadratic residues.
Question: Before looking at it, do you see why a quadratic residue automatically can't be a primitive root? (This follows from a result above.)
Here is another way to view the tension between primitive roots and quadratic residues. All the residues are the second column (labeled 1), and all the quadratic residues are the colors in the third column (labeled 2 as they are squares). See how that column is symmetric about the middle of the rows, with two of each of the colors appearing. Note that these are the same colors as every other column in a row with a primitive root (the rows with every color represented), though not necessarily in that order. Also notice that the color of the middle column determines whether the color beginning that row shows up in the second column. Weird! Yet true.
Here's a final fun thing. What is the sum of all Legendre symbols for a given prime?
This is cool, and a nice example of the kind of fun one can have experimenting. What do you think? Do you think we can prove it?