The previous section should really resolve that examining square roots suffices to a complete solution, so that is what not only the remainder of this chapter, but the next chapter, will focus on.
We now introduce two definitions, a little more formal in nature.
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\).
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.
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.
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.
This last function gives the smallest nonresidue, in case you need it.
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\)?
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.
What do you think? Do you see any patterns?
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!
In fact, it is even hard to conjecture such things 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 for the paper. Note that if you read it carefully, you will have hints to the question in the previous subsection, with regard to numbers of the form \(a^2+2b^2\)!
Euler archive listing
Euler archive translation
Euler's work explained by Ed Sandifer
Next, look at a table made by the great Italian-French mathematician Lagrange, courtesy of the French National Library and its online repository, Gallica.
In this table, Lagrange is referring to integers of the form \(t^2+au^2\), 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\). (See the discussion around Theorem 13.5.5.) And if you were diligent in your pattern searching in the previous subsection, you will have found the significance for \(8n+1\) and \(8n+3\) with respect to \(t^2+2u^2\). (For more on this and its history, see the excellent book Mathematical Masterpieces [C.4.7].)
Originally from what is now Italy, Lagrange was Euler's successor in Berlin after he 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\), \(a^2+2b^2\), etc.) that Fermat and Euler talked about. Although he isn't always mentioned as highly as other contemporaries like Euler or Gauss, note that we've already seen two of his theorems (7.4.1 and 8.3.11). Later he moved to France and was quite influential there. 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!
