Quadratic Residues

Integers which are perfect squares are rare; only about \( \frac1{\sqrt{x}} \) of the integers in the set \( \{ 1, 2, \ldots, x \} \) are perfect squares. On the other hand, given an odd prime \( p \), integers that are squares modulo \( p \) are relatively common. In fact, it turns out that exactly half of the integers between \( 1 \) and \( p-1 \) are squares mod \( p \); that is, the congruence \( x^2 \equiv a \) mod \( p \) has a solution \( x \) for exactly half of the values of \( a \) in \( \{ 1, 2, \ldots, p-1 \} \).

If \(a\) and \(m\) are coprime integers, then \(a\) is called a quadratic residue modulo \(m\) if the congruence \(x^2\equiv a\pmod m \) has a solution.

Likewise, if it has no solution, then it is called a quadratic non-residue modulo \(m\).

The natural next question is "Given \(m,\) what are the quadratic residues mod \(m\)?" This question and its answer are of great interest in number theory and cryptography.

Find the quadratic residues mod \( 11 \).

---

When \(x = 0\), \(x^2 \bmod 11 = 0^2 \bmod 11 = 0 \).
When \(x = 1\), \(x^2 \bmod 11 = 1^2 \bmod 11 = \color{green}1 \).
When \(x = 2\), \(x^2 \bmod 11 = 2^2 \bmod 11 = \color{blue}4 \).
When \(x = 3\), \(x^2 \bmod 11 = 3^2 \bmod 11 = \color{orange}9 \).
When \(x = 4\), \(x^2 \bmod 11 = 4^2 \bmod 11 = \color{brown}5 \).
When \(x = 5\), \(x^2 \bmod 11 = 5^2 \bmod 11 = \color{#318CE7}3 \).
When \(x = 6\), \(x^2 \bmod 11 = 6^2 \bmod 11 = \color{#318CE7}3 \).
When \(x = 7\), \(x^2 \bmod 11 = 7^2 \bmod 11 = \color{brown}5 \).
When \(x = 8\), \(x^2 \bmod 11 = 8^2 \bmod 11 = \color{orange}9 \).
When \(x = 9\), \(x^2 \bmod 11 = 9^2 \bmod 11 = \color{blue}4 \).
When \(x = 10\), \(x^2 \bmod 11 = 10^2 \bmod 11 = \color{green}1 \).

So the quadratic residues mod \( 11 \) are \(1,3,4,5,9 \), and the non-residues are \( 2,6,7,8,10\). \(_\square\)

Note: A number that is congruent to 0 mod p is neither a residue nor a non-residue.

Notice that the numbers that are colored above are in the order of \(\{1,4,9,5,3,3,5,9,4,1\} \). That is,

• the first number and the last number are equal;
• the second number and the second last number are equal;
• the third number and the third last number are equal, and so on.

This is because \(x^2 \equiv (-x)^2 \pmod p \). So the squares of the first half of the nonzero numbers mod \( p \) give a complete list of the nonzero quadratic residues mod \( p \). In general,

Fact: If \( p \) is an odd prime, the residue classes of \(0^2,1^2,2^2,\ldots, \left(\frac{p-1}2\right)^2 \) are distinct and give a complete list of the quadratic residues modulo \(p\). So there are \( \frac{p+1}2 \) residues and \( \frac{p-1}2 \) non-residues.

Proof: They give a complete list because \( x^2 \) and \( (p-x)^2 \) are the same mod \( p \) as in the example. To see that they are distinct, note that \[ \begin{align} x^2 \equiv y^2 \pmod p &\Leftrightarrow p|x^2-y^2 \\ &\Leftrightarrow p|(x-y)(x+y) \\ &\Leftrightarrow p|(x-y) \ \text{or} \ p|(x+y), \end{align} \] which is impossible if \( x \) and \( y \) are two different members of the set \( \left\{ 0, 1, 2, \ldots, \frac{p-1}2 \right\} \). \(_\square \)

Let \( p \) be a prime. Show that the congruence \( x^2+y^2+1 \equiv 0 \) mod \( p \) always has a solution \((x,y)\).

---

It is clear for \( p =2 \), so assume \( p \) is odd. The above work shows that there are \( \frac{p+1}2 \) elements of \( \{ 0,1,\ldots,p-1 \} \) that can be written as \( x^2 \) mod \( p \), and for the same reason there are \( \frac{p+1}2 \) elements of \( \{0,1,\ldots,p-1 \} \) that can be written as \( -1-y^2 \) mod \( p \). Since the sum of the sizes of these two subsets is \( p+1 \) and \( \{0,1,\ldots,p-1\} \) has \( p \) elements, the two subsets must overlap somewhere, i.e. \[ x^2 \equiv -1-y^2 \pmod p \Leftrightarrow x^2+y^2+1 \equiv 0 \pmod p \] for some \(x,y\). \(_\square \)

The above result happens to be a key lemma in the proof of Lagrange's famous four squares theorem, which states that every positive integer can be written as a sum of four integer squares. (See Sum of Squares Theorems.)

The techniques used to compute quadratic residues mod \( p \) are contained in the article on Legendre symbols. This section focuses on general quadratic Diophantine equations, including situations where the modulus is not prime.

For quadratic Diophantine equations, completing the square is often helpful.

Determine whether there exists an integer \(x\) such that \(37 \) divides \( x^2 - 31x + 34\).

---

Modulo 37, we have \[x^2 -31 x + 34 \equiv x^2 + 6x -3 = x^2 + 6x + 9 - 12 = (x+3)^2 - 12. \] So this has a solution if and only if \( 12 \) is a quadratic residue mod \( 37 \). By inspection, \( 7^2 \equiv 12 \) mod \( 37 \), so the equation has solutions; setting \( x+3 = 7 \) gives \( x = 4 \) as one of them. \(_\square\)

For composite modulus, the Chinese remainder theorem is an important tool to break the problem down into prime power moduli.

Determine the number of positive integers \(x\) less than 1000 such that when \( x^2 \) is divided by 840, it leaves a remainder of 60.

---

Converting it into a congruence, we have \(x^2 \equiv 60 \pmod{840} \). Factoring 840 into a product of prime powers gives \(840=3\cdot 5\cdot 7\cdot 8 \).

So we have \(x^2 \equiv 0 \pmod 3,x^2 \equiv 0 \pmod 5,x^2 \equiv 4 \pmod 7,x^2 \equiv 4\pmod 8 \).

The first two congruences imply \( x^2 \equiv 0 \) mod \( 15 \).
Solving the other two congruences shows that \(x\equiv \pm \ 2\pmod 7, x \equiv \pm \ 2 \pmod 8 \).

By the Chinese remainder theorem, \(x \equiv 2,26,30,54 \pmod{56} \) and \( x \equiv 0 \) mod \( 15 \).
By the Chinese remainder theorem again, \( x \equiv \pm 30, \pm 390 \) mod \( 840 \).

With the restriction of \(0 < x < 1000\), there are \( 5 \) solutions in all: \(x = 30, 390, 450, 810, 870 \). \(_\square\)

Modular Arithmetic
Chinese Remainder Theorem
Legendre Symbol
Law of Quadratic Reciprocity