Section16.3Quadratic residues

So we really just need to look at square roots. And that's where we'll go next! We now introduce two definitions, a little more formal in nature.

Definition16.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\).

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 that the equivalence classes \([a]\) are called residues, so one which is a square is quadratic.

Remark16.3.2

Sage note:
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.

Subsection16.3.1First Try for Square Roots of Two

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? Then we'll look at more data.

What do you think? Any patterns?

As it turns out, it is quite hard to prove such patterns 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!

Subsection16.3.2Some history

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. Here are three links for a very unusual paper of Euler's - one where he included nary a proof, just closely related conjectures to this question!

Next, look at the handout of more tables made by the great Italian-French mathematician Lagrange.

  • 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.
  • We already know two of his theorems.
  • 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.
  • Lagrange was Euler's successor in Berlin after he went back to Russia under the stable (if despotic) regime of Catherine the Great; later he moved to France and was quite influential there.
What is important to note about these tables is that although they are looking at divisors of numbers of the form \(t^2\pm au^2\), it is closely related to our question. When \(u=1\), such divisors are numbers that are a modulus where \(a\) is a perfect square.

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.