What made the theory of quadratic residues/square roots work out best in the end was a couple of key innovations of the French mathematician Adrien-Marie Legendre; Gauss in particular made great use of them.
was Lagrangeβs successor in Paris. 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 historian of mathematics Judith Grabiner argues led to rigorization of calculus), he wrote a widely used geometry textbook.
While approaching the topic historically can be beneficial, since we have the advantage of having developed the basics of groups and primitive roots, we will be able to simplify the exposition of quadratic residues a great deal by (somewhat anachronistically) using these concepts.
The set of (non-zero) quadratic residues modulo a prime really is a group, and is even a subgroup of the group of units .
Proof.
We will proceed by showing the group axioms hold under multiplication. Since we exclude zero and is prime, is a subset of essentially by definition, which will imply it is a subgroup of as well.
Letβs look at the three main axioms.
It is clear that , since . So there is an identity.
Next, if and are both in (with and ), then is also a quadratic residue (since ).
All that remains is to check that this set has inverses under multiplication.
To show this last point, assume that , and consider as an element of . Then
For those with some additional algebraic background, it turns out is in fact a quotient group of as well, but we will not delve further into this here.
You might be wondering how this piece of connects to the most important thing weβve seen so far about . Recall that was cyclic, that it had a generator whose powers gave us all units modulo . We called such an element a primitive root of (recall Chapter 10).
So letβs compare the primitive rootβs powers and the quadratic residues. Shouldnβt be too hard β¦ if you arenβt computing this with Sage, just try it by hand with an even smaller modulus, like seven or eleven.
For odd prime modulus , the quadratic residues are precisely the even powers of a primitive root .
Proof.
Certainly , so the even powers of are QRs.
Now we need the other set inclusion. Suppose that and . Then first note that and are themselves still powers of (by definition of ). So let and for some . Then we have the implication
(mod (mod .
This is only possible if is even since and are even.
This is a very strong statement, because it does not depend upon the primitive root! For example, if , one can verify both and are primitive roots modulo eleven; then they are clearly nonresidues, and moreover are odd powers of each other:
This fact will turn out to be a fantastically useful theoretical way to find . It will show up in lots of proofy settings. Here is a first example, a very nice result about when a composite number is a QR.
If is a factorization (not necessarily nontrivial) of , then is a QR of precisely when either both and are QRs of or both and are not QRs of .
Proof.
Modulo , write and for some . Then , and is even when and have the same parity. Because of Fact 16.4.5, this is exactly the same thing as the conclusion of the proposition.
Our first step is to try to make a product of two numbers we already know something about. Since (mod ), we can look at and separately. Then recall that is not a QR (since (mod )) but is, from our explorations. So we would conjecture is not a QR either.
We can use the same trick for other numbers congruent to modulo . For instance, I can immediately decide that is a QR (mod ) by the fact that neither nor is a QR modulo .
There is yet another way to view the tension between primitive roots and quadratic residues. Before moving on to the next interactive graphic, try to answer the following question.
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.10.)
The second column (labeled 1) contains all the residues, and by definition the quadratic residues are the colors located 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 QR colors appearing. Further, these are the same colors as the ones appearing in every other column in rows with a primitive root (the rows with every color represented); naturally, the order may be quite different. Finally, the second columnβs color in each row that has every color (including black) never shows up in the third column (the one for squares); this corresponds to the fact that a primitive root canβt be a quadratic residue.
These observations may not seem as interesting, but they will pay off; in the next section we will obtain a crucial criterion for computing quadratic residues by observing a similar pattern!