Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section16.4Send in the Groups

What made things work out best in the end was a couple innovations of Lagrange's successor in Paris, Adrien-Marie Legendre. These were innovations Gauss made great use of.

One can approach this subject from many vantage points, including the historical one. However, we have the advantage of having developed the basics of groups and primitive roots, which will simplify much of our exposition.

Subsection16.4.1Quadratic residues form a group

Definition16.4.1

Consider the set of all non-zero quadratic residues modulo some prime \(p\). We call this the group of quadratic residues \(Q_p\).

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

Proof
Remark16.4.3

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

Subsection16.4.2Quadratic 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\). Recall that \(U_p\) was cyclic, that it had a generator whose powers gave us all units modulo \(p\). We called such an element a primitive root of \(p\) (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 with an even smaller modulus, like seven.

Note the pattern! This exemplifies a major fact.

Proof

This fact will turn out to be a fantastically useful theoretical way to find \(Q_p\). It will show up in lots of proofy settings.