NTIC Quadratic Residues

🔗

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²The now-standard terminology for nonresidues can cause confusion. For example, at this writing (2020) 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.

xxxxxxxxxx
 
quadratic_residues(17)

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.

xxxxxxxxxx
 
least_quadratic_nonresidue(17)

🔗

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.

xxxxxxxxxx
 
@interact
def _(odd_primes_up_to=50):
    for p in prime_range(3,odd_primes_up_to):
        solutions=solve_mod([x^2==2],p)
        if len(solutions)!=0:
            pretty_print(html(r"$x^2\equiv 2\text{ (mod }%s)$ has solutions $%s$ and $%s$"%(p,solutions[0][0],solutions[1][0])))
        else:
            pretty_print(html("No solutions modulo $%s$"%p))

🔗

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

Euler archive listing for original paper
Euler archive translation of the paper into English
Euler's work in this paper explained by Ed Sandifer (focusing on the cases $a^2+nb^2$ )

🔗

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 [C.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.

🔗

Remark 16.3.7.

Originally from what is now Italy, Lagrange was Euler's successor in Berlin 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!

Number Theory: In Context and Interactive

Section 16.3 Quadratic Residues