Skip to main content

Section 16.3 Quadratic Residues

As the previous section makes clear, my belief is that finding when square roots exist (mostly for odd modulus) is the core of finding a complete solution. The remainder of this chapter and most of the next will focus on resolving this question.

Subsection 16.3.1 Some definitions

We first introduce two definitions, a little more formal in nature.

Definition 16.3.1.

Assume that \(a\not\equiv 0\) (mod \(p\)), for \(p\) a prime.

  • If there is a solution of \(x^2\equiv a\) (mod \(p\)) we say that \(a\) is a quadratic residue of \(p\) (or a QR).

  • If there is not a solution of \(x^2\equiv a\) (mod \(p\)) we say that \(a\) is a quadratic nonresidue of \(p\text{.}\)

Although some authors also define this notion for composite moduli (as does Sage, see Sage note 16.3.3), we will go with the majority of them and reserve these terms for prime moduli.

Note that this is the same thing as saying that \(a\) does or does not have a square root modulo \(p\text{,}\) but the focus changes to \(a\) instead of the square root itself.

It is not so easy at all to determine even when something is a QR, much less to compute the square roots, so we will take some significant time on this.

Remark 16.3.2.

By the way, the terminology is explained by the fact (recall Section 4.4) that the equivalence classes \([a]\) are called residues, so one which is a perfect square is justly called quadratic 2 .

The now-standard terminology for nonresidues can cause confusion. For example, at this writing (January 2021) the Wikipedia page for a related concept used both ‘quadratic nonresidue’ and ‘non-quadratic residue’. But the Google Ngram Viewer suggests that most academic mathematicians now use ‘quadratic nonresidue’. Then again, some older papers (including one by Sylvester) definitely use the term, as well as at least one instance on the OEIS and some newer books, so perhaps there is an interesting paper on the linguistics of higher mathematics waiting to be written.
Sage note 16.3.3. Quadratic residues.

Sage can calculate these for us, of course.

Notice that Sage counts zero as a quadratic residue (since \(0^2=0\) always); there are technical reasons not to consider it as one in our theoretical treatment, as will be seen soon.

A separate function gives the smallest nonresidue, in case you need it.

Subsection 16.3.2 First try for new square roots

To get more of a flavor for this, let's explore for which \(p\) it is true that \(x^2\equiv 2\) (mod \(p\)) has a solution. Or, to put it another way, when does two have a square root modulo \(p\text{?}\)

First do some by hand; for what primes up to 20 does \(2\) have a square root?

Once you've done this, then evaluate the next Sage cell to look at more data.

Question 16.3.4.

What do you think? Do you see any patterns in when a square root of two exists?

As it turns out, it is quite hard to prove any such patterns you may find without the benefit of powerful theoretical machinery. Which means it is hard to even know whether there is a solution to a given congruence without such machinery!

Subsection 16.3.3 Some history

In fact, it is even hard to conjecture patterns for harder cases unless you are quite clever. Euler was one of the first to do so. In a very unusual paper, he included nary a proof, just closely related conjectures to this question.

We list here three links related to the paper. Note that if you read it carefully, you will have hints to a solution of Question 16.3.4 in the previous subsection; look for numbers of the form \(a^2-2b^2\text{.}\)

Next, look at two tables made by the great Italian-French mathematician Lagrange, courtesy of the French National Library and its online repository, Gallica.

Figure 16.3.5. Lagrange's Table III from “Recherches d'arithmétique”

In Figure 16.3.5, Lagrange is referring to integers of the form \(t^2+au^2\text{,}\) and then what form their divisors can have. That this corresponds to what we have seen is clear in that \(a=1\) just means that primes can divide a sum of squares if they are themselves of the form \(y^2+z^2\) when they are of the form \(4n+1\text{.}\) (See the discussion around Theorem 13.5.5.) For more on these tables and their history, see the excellent book Mathematical Masterpieces [E.5.7].

Figure 16.3.6. Lagrange's Table IV from “Recherches d'arithmétique”

In Figure 16.3.6, Lagrange is referring to divisors of integers of the form \(t^2-au^2\) instead. When \(a=2\text{,}\) this should correspond to primes for which one may have a square root of two. Note that the formulas for the divisors are for \(4an+b\text{,}\) so that when \(a=2\text{,}\) the table says that we will have (odd) prime divisors of the form \(8n\pm 1\) (and only that form). Does this correspond with your pattern searching in the previous subsection?

See also Theorem 42 of Euler's paper, and Theorem 16.7.1 where we will confirm this pattern.

Historical remark 16.3.7. Joseph-Louis Lagrange.

Originally from what is now Italy, Lagrange was Euler's successor in Berlin in the court of Frederick the Great, after Euler went back to Russia under the stable (if despotic) regime of Catherine the Great. One interesting point to make about him is that Lagrange gave proofs of many of the patterns in quadratic forms (what numbers look like \(a^2+b^2\text{,}\) \(a^2+2b^2\text{,}\) etc.) that Fermat and Euler talked about.

Although he isn't always mentioned quite as highly in the undergraduate literature as his contemporaries Euler or Gauss, note that we've already seen two of his theorems (7.4.1 and 8.3.12), and Euler himself anointed him as the best mathematician in Europe. Later he moved to France and remained quite influential (as well as managing to survive the Terror, which was not true for all academics at the time). And if you ever read any science fiction or space stuff that talks about stable places to orbit being called Lagrange points – that's him too!