Section 16.4 Send in the Groups
Historical remark 16.4.1. Adrien-Marie Legendre.
Legendre 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.
Subsection 16.4.1 Quadratic residues form a group
Definition 16.4.2.
Consider the set of all non-zero quadratic residues modulo some prime
Theorem 16.4.3.
The set of (non-zero) quadratic residues
Proof.
We will proceed by showing the group axioms hold under multiplication. Since we exclude zero and \(p\) is prime, \(Q_p\) is a subset of \(U_p\) essentially by definition, which will imply it is a subgroup of \(U_p\) as well.
Let's look at the three main axioms.
It is clear that \(1\in Q_p\text{,}\) since \(1\equiv 1^2\text{.}\) So there is an identity.
Next, if \(a\) and \(b\) are both in \(Q_p\) (with \(a\equiv s^2\) and \(b\equiv t^2\)), then \(ab\) is also a quadratic residue (since \((st)^2\equiv s^2 t^2\equiv ab\)).
All that remains is to check that this set has inverses under multiplication.
To show this last point, assume that \(a\equiv s^2\in Q_p\text{,}\) and consider \(s^{-1}\) as an element of \(U_p\text{.}\) Then
So by definition of inverses
which means that if \(a\in Q_p\) then \(a^{-1}\in Q_p\) as well.
Remark 16.4.4.
For those with some additional algebraic background, it turns out
Subsection 16.4.2 Quadratic residues connect to primitive roots
You might be wondering how this piece ofxxxxxxxxxx
g=mod(primitive_root(19),19); g
xxxxxxxxxx
g=mod(primitive_root(19),19)
L=[g^n for n in range(1,19)]
print(L)
print(quadratic_residues(19))
Fact 16.4.5.
For odd prime modulus
Proof.
Certainly \(g^{2n}=\left(g^n\right)^2\text{,}\) so the even powers of \(g\) are QRs.
Now we need the other set inclusion. Suppose that \(a\in Q_p\) and \(a=s^2\text{.}\) Then first note that \(s\) and \(a\) are themselves still powers of \(g\) (by definition of \(g\)). So let \(s=g^n\) and \(a=g^m\) for some \(n,m\text{.}\) Then we have the implication
This is only possible if \(m\) is even since \(p-1\) and \(2n\) are even.
Example 16.4.6.
This is a very strong statement, because it does not depend upon the primitive root! For example, if
Proposition 16.4.7.
If
Proof.
Modulo \(p\text{,}\) write \(a\equiv g^i\) and \(b\equiv g^j\) for some \(i,j\text{.}\) Then \(n=ab\equiv g^{i+j}\text{,}\) and \(i+j\) is even when \(i\) and \(j\) have the same parity. Because of Fact 16.4.5, this is exactly the same thing as the conclusion of the proposition.
Example 16.4.8.
Let's assume that we have the pattern observed in Question 16.3.4 and try to decide whether
Our first step is to try to make
xxxxxxxxxx
quadratic_residues(23)
We can use the same trick for other numbers congruent to
xxxxxxxxxx
quadratic_residues(11)
We will soon revisit this idea in Proposition 17.1.1.
Question 16.4.9.
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.)

xxxxxxxxxx
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
def power_table_plot(p=(13,prime_range(50)[2:])):
mycmap = plt.get_cmap('gist_earth',p-1)
myloc = IndexLocator(floor(p/5),.5)
myform = FuncFormatter(lambda x,y: int(x+1))
cbaropts = { 'ticks':myloc, 'drawedges':True, 'boundaries':srange(.5,p+.5,1)}
P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p+1)]),cmap=mycmap, colorbar=True, colorbar_options=cbaropts, ticks=[myloc,myloc], tick_formatter=[None,myform])
show(P,figsize=6)