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≢0 (mod p), for p a prime.

  • If there is a solution of x2≡a (mod p) we say that a is a quadratic residue of p (or a QR).

  • If there is not a solution of x2≡a (mod p) we say that a is a quadratic nonresidue of p.

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, 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 02=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 x2≡2 (mod p) has a solution. Or, to put it another way, when does two have a square root modulo p?

🔗
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 a2−2b2.

🔗
Next, look at two tables made by the great Italian-French mathematician Lagrange, courtesy of the French National Library and its online repository, Gallica. (The license does not allow for commercial use of these images.)

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 t2+au2, 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 y2+z2 when they are of the form 4n+1. (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 t2−au2 instead. When a=2, 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, so that when a=2, the table says that we will have (odd) prime divisors of the form 8n±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 a2+b2, a2+2b2, 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!