NTIC Send in the Groups

Section 16.4 Send in the Groups

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.

🔗

Remark 16.4.1.

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.

🔗

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.

🔗

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 $p\text{.}$ We call this the group of quadratic residues $Q_p\text{.}$

🔗

This terminology suggests that I have a proof in my pocket for the following theorem.

🔗

Theorem 16.4.3.

The set of non-zero quadratic residues $Q_p$ modulo a prime $p$ really is a group, and is even a subgroup of the group of units $U_p\text{.}$

🔗

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{.}$ Then note that

\begin{equation*} \left(s^{-1}\right)^2 a\equiv \left(s^{-1}\right)^2 s^2\equiv \left(s\cdot s^{-1}\right)^2\equiv 1 \end{equation*}

So by definition of inverses

\begin{equation*} \left(s^{-1}\right)^2=a^{-1}\text{,} \end{equation*}

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 $Q_p$ is in fact a quotient group of $U_p$ as well, but we will not delve further into this here.

🔗

Subsection 16.4.2 Quadratic residues connect to primitive roots

🔗

You might be wondering how this piece of

$U_p$ connects to the most important thing we've seen so far about

$U_p\text{.}$ Recall that

$U_p$ was cyclic, that it had a generator whose powers gave us all units modulo

$p\text{.}$ We called such an element a primitive root of

$p$ (recall Chapter 10).

xxxxxxxxxx
 
g=mod(primitive_root(19),19); g

🔗

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.

xxxxxxxxxx
 
g=mod(primitive_root(19),19)
L=[g^n for n in range(1,19)]
print(L)
print(quadratic_residues(19))

🔗

Note the pattern of which elements of

$U_{19}$ (as powers of the primitive root) are quadratic residues! This exemplifies a major fact.

🔗

Fact 16.4.5.

For odd prime modulus $p\text{,}$ the quadratic residues are precisely the even powers of a primitive root $g\text{.}$

🔗

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

\begin{equation*} a=g^m\equiv g^{2n}\text{ (mod }p) \Longrightarrow m\equiv 2n\text{ (mod }p-1)\text{.} \end{equation*}

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 $p=11\text{,}$ one can verify both $2$ and $8$ are primitive roots modulo eleven; then they are clearly nonresidues, and moreover are odd powers of each other:

$\begin{equation*} 8^1\equiv 2^3\text{ and }2^1\equiv 8^7\text{ (mod }11)\text{.} \end{equation*}$

🔗

This fact will turn out to be a fantastically useful theoretical way to find

$Q_p\text{.}$ 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.

🔗

Proposition 16.4.7.

If $n=ab$ is a factorization (not necessarily nontrivial) of $n\text{,}$ then $n$ is a QR of $p$ precisely when either both $a$ and $b$ are QRs of $p$ or both $a$ and $b$ are not QRs of $p\text{.}$

🔗

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.

🔗

Hence if one of

$a,b$ is a QR and the other one isn't, neither is

$n=ab\text{.}$

🔗

Example 16.4.8.

Let's assume that we have the pattern observed in Question 16.3.4 and try to decide whether $21$ is a QR (mod $23$ ).

Our first step is to try to make $21$ a product of two numbers we already know something about. Since $21\equiv -2$ (mod $23$ ), we can look at $-1$ and $2$ separately. Then recall that $-1$ is not a QR (since $23\equiv 3$ (mod $4$ )) but $2$ is, from our explorations. So we would conjecture $21$ is not a QR either.

xxxxxxxxxx
 
quadratic_residues(23)

We can use the same trick for other numbers congruent to $-2$ modulo $p\text{.}$ For instance, I can immediately decide that $-2\equiv 9$ is a QR (mod $11$ ) by the fact that neither $-1$ nor $2$ is a QR modulo $11\text{.}$

xxxxxxxxxx
 
quadratic_residues(11)

We will soon revisit this idea in Proposition 17.1.1.

🔗

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.

🔗

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

🔗

Now try our familiar graphic again, this time concentrating on which rows correspond to primitive roots and which ones to quadratic residues.

🔗

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.

🔗

Try it out interactively until the connection between the known facts and the graphical pattern seems plausible.

xxxxxxxxxx
 
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
@interact
def power_table_plot(p=(13,prime_range(50))):
    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)

🔗

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!