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 Theorem 16.5.1.
Like many mathematicians of the eighteenth century, Legendre worked in many areas, including function theory and mathematical physics. Notably, as increased professionalization of studies of higher mathematics came about in post-Revolutionary French engineering studies (a development Judith Grabiner argues led to rigorization of calculus), he wrote a widely used geometry textbook.
What of the plus or minus 1? To quote an article [C.6.5] on this subject, 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.
―Steven H. Weintraub
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.)
We write \(\left(\frac{a}{p}\right)\) for the Legendre symbol. \begin{equation*}\left(\frac{a}{p}\right)=1\text{ if }a\text{ is a QR modulo }p\text{ and }\left(\frac{a}{p}\right)=-1\text{ if it's not.}\end{equation*} We define the Legendre symbol of \(a\) modulo \(p\) to be zero if \(p\mid a\).
We can restate Fact 16.1.2: We have that \(\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 in Definition 16.3.1, especially since Sage includes zero as a QR.
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\).)
Let's use our usual example to visualize the tension and connection between primitive roots and quadratic residues.
Before looking at the next graphic, do you see why a quadratic residue automatically can't be a primitive root? (This follows from results earlier in this chapter; see Exercise 16.8.7.)
There is another way to view the tension between primitive roots and quadratic residues. Try the following graphic yet again.
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. This seems weird – but is precisely the content of Section 16.5.
Here's a final fun thing. What is the sum of all Legendre symbols for a given prime? (As usual, you can do this by hand for small primes if you aren't computing.)
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? Try in Exercise 16.8.6.
