6 Quadratic residues
We’re now going to investigate what the image of the squaring map \(x \mapsto x^2\) on \(\mathbb{Z}/ m\mathbb{Z}\) looks like. The elements which are in the image have a special name:
Definition 6.1
We say \(a \in \mathbb{Z}/ m\mathbb{Z}\) is a quadratic residue (QR) modulo \(m\) if there exists \(x \in \mathbb{Z}/ m\mathbb{Z}\) with \(x^2 = a.\)
For example, in \(\mathbb{Z}/ 6\mathbb{Z},\) we have \[\begin{array}{r|rrrrrr} \text{$x$} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \text{$x^2$} & 0 & 1 & 4 & 3 & 4 & 1 \end{array}\] so \(\{0, 1, 3, 4\}\) are quadratic residues mod 6, and \(\{2, 5\}\) are not.
6.1 Reducing to the prime case
From the Chinese remainder theorem, it’s clear that if \(n = \prod_i p_i^{e_i},\) then \(a\) is a QR mod \(n\) iff it’s a QR modulo \(p_i^{e_i}\) for all \(i.\) Rather less obvious is the following:
Proposition 6.2
Let \(p \in \mathbb{P}\) with \(p > 2,\) and let \(a \in \mathbb{Z},\) with \(p \nmid a.\) If \(a\) is a QR mod \(p,\) then \(a\) is a QR mod \(p^k,\) for every \(k \geqslant 1.\)
Proof. Let’s prove this by induction on \(k,\) the case \(k = 1\) being true by assumption. So suppose \(b \in \mathbb{Z}\) is such that \(b^2 = a \bmod p^k,\) for some \(k \geqslant 1,\) and let’s try to cook up a solution modulo \(p^{k+1}.\)
By assumption, we have \(b^2 = a + p^k r,\) for some \(r.\) Let’s consider integers of the form \(b' = b + p^k s.\) Then we have \[(b')^2 = (b + p^k s) ^ 2 = (a + p^k r) + 2 b p^k s + p^{2k} s^2\] and modulo \(p^{k+1}\) this is just \(a + p^k (r + 2 b s).\) So it suffices to show that we can choose \(s\) such that \(r + 2 b s = 0 \bmod p.\)
Since \(b^2 = a \ne 0 \bmod p,\) and \(p \ne 2,\) it follows that \(2b\) is a unit mod \(p,\) and we are done.
Remark 6.3
The argument breaks down for \(p = 2\): if \(a = 5,\) then \(a\) is a QR modulo 2 and modulo 4, but not modulo 8. However, one can adapt the proof to show that an odd integer is a QR modulo every power of 2 iff it is 1 mod 8.
The argument above is a preview of a much more general theorem called Hensel’s Lemma which we’ll see in the last chapter of the course.
6.2 QRs modulo primes
We can now concentrate on quadratic residues when the modulus is a prime \(p\) with \(\mathbf{p \ne 2}\) We first note that any nonzero quadratic residue mod \(p\) always has exactly 2 square roots mod \(p\) (if \(x\) is one, then \(-x\) is the other, and \(x \ne -x\)). Since each unit mod \(p\) has to square to something, it follows that there are exactly \((p-1)/2\) nonzero quadratic residues; in other words, exactly half of the elements of \(U_p\) are squares.
Definition 6.4
Let \(p\) be an odd prime, and \(a \in \mathbb{Z}.\) Then the Legendre symbol is defined by \[\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if $a = 0 \bmod p$},\\ 1 & \text{if $a$ is a nonzero quadratic residue mod $p,$}\\ -1 & \text{if $a$ is a non-residue mod $p$}. \end{cases}\]
Then we have the following:
Theorem 6.5 • Euler, 1748
We have \[\left(\frac{a}{p}\right) = a^{(p-1)/2} \bmod p.\]
Proof. If \(a = 0 \bmod p\) the result is obvious, so assume \(p \nmid a.\) Then \(\left(a^{(p-1)/2}\right)^2 = 1 \bmod p\) by Fermat’s little theorem, so \(a^{(p-1)/2}\) must be either \(1\) or \(-1\) modulo \(p.\)
If \(a = b^2 \bmod p\) for some \(x,\) then \(a^{(p-1)/2} = b^{(p-1)} = 1,\) again by Fermat’s little theorem. So every nonzero QR is a root of \(X^{(p-1)/2} - 1 = 0.\) However, since this polynomial has degree \((p-1)/2,\) and we’ve just exhibited \((p-1)/2\) roots of it, there can’t be any more. So all quadratic non-residues \(a\) must satisfy \(a^{(p-1)/2} = -1 \bmod p.\)
Here’s an easy consequence:
Proposition 6.6
\(-1\) is a quadratic residue modulo the odd prime \(p\) if \(p = 1 \bmod 4,\) and a non-residue if \(p = 3 \bmod 4.\) 0◻
Another important consequence is the multiplicativity of the Legendre symbol:
Corollary 6.7
For any integers \(a, b\) we have \[\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right).\]
Proof. Since both sides are equal to \(0\) or \(\pm 1,\) and \(p > 2,\) it suffices to show that \(\left(\frac{ab}{p}\right)\) and \(\left(\frac{a}{p}\right) \left(\frac{b}{p}\right)\) are congruent mod \(p.\) But this follows from Euler’s criterion and the formula \[(ab)^{(p-1)/2} = a^{(p-1)/2} b^{(p-1)/2}.\]
Remark 6.8
It’s quite a strange and surprising thing that the product of two non-squares is always a square. This can be seen in an elementary way as follows. Take \(a \in U_p\) which isn’t a square, and consider the map \(U_p \to U_p\) sending \(b\) to \(ab.\) This is a bijection; and it sends squares to non-squares, because if \(b = x^2\) and \(ab = y^2\) are both (nonzero) squares, then \(a = (y / x)^2\) would have to be a square itself.
Since there are equally many squares and non-squares, that “uses up” all the possible non-square images. Hence the non-squares have to go to squares, i.e. if \(b\) is non-square then \(ab\) is square.
Exercise 6.9
How many quadratic residues are there mod 15? How many of the units mod 15 are quadratic residues?
Give an example of integers \(a, b\) such that \(a,\) \(b\) and \(ab\) are all units and all quadratic non-residues mod 15.
Exercise 6.10
Suppose that there are finitely many primes \(p\) with \(p = 1 \bmod 4.\) By considering the integer \(4 (p_1 \dots p_k)^2 + 1\) where \(\{p_1, \dots, p_k\}\) is the set of all such primes, deduce a contradiction.