In Why study Diophantine equations?, we discussed studying polynomial equations in modular arithmetic. One of the first equations encountered in high school algebra is the quadratic equation \[ax^2 + bx + c = 0.\] It is thus natural to ask about the modular arithmetic version: if \(a, b, c\) are integers, and \(n\) is another integer, what are the solutions to \[ax^2 + bx + c \equiv 0 \pmod{n}?\]
In high school algebra, to solve the quadratic equation, we start by noticing that life would be much easier if \(b = 0,\) since then our quadratic equation is just \[ax^2 + c = 0,\] which is solved by \[x = \pm\sqrt{-\frac{c}{a}}.\]
Fortunately, we can always reduce to the case where \(b=0,\) by completing the square. That is, we can rewrite our equation \[ax^2 + bx + c = 0\] as \[a\left(x + \frac{b}{2a}\right)^2 + \left(c - \frac{b^2}{4a}\right) = 0,\] so that \[x + \frac{b}{2a} = \pm \sqrt{\frac{c - \frac{b^2}{4a}}{a}}.\] Cleaning up this equation a little bit gives us the familar-looking quadratic formula \[x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}.\]
So, how would we solve an equation like \[2x^2 - 3x + 5 \equiv 0 \pmod{15}?\]
We can repeat the completing-the-square trick to see the solutions are \[x \equiv \frac{3 \pm \sqrt{3^2 - 4\cdot 2 \cdot 5}}{2 \cdot 2} \equiv \frac{3 \pm \sqrt{-31}}{4} \pmod{15}.\] In What is \(\log(3)\) modulo \(7\)?, we discussed finding square roots, and doing division, in modular arithmetic. The key point was that, because \[8 \cdot 2 \equiv 1 \pmod{15},\] we should treat \(8\) as \(1/2.\) And in particular, division by 2 is the same as multiplication by 8. Thus division by 4 is the same as multiplication by \(8^2 = 64 \equiv 4\pmod{15},\) so we can rewrite our quadratic formula as \[x \equiv 12 \pm 4\sqrt{-31} \pmod{15}.\] The other challenge now is to find some integer \(y\) so that \(y^2 \equiv -31 \pmod{15}.\) In other words, we want to solve \[y^2 \equiv 14 \pmod{15}.\]
But in fact, this equation has no solutions! Any solution must also satisfy \[y^2 \equiv 14 \pmod{3},\] meaning \[y^2 \equiv 2 \pmod{3}.\] But we can compute all the squares modulo 3: \[0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 1 \pmod{3},\] and we find that no matter what residue you square modulo 3, you will never get 2.
With the same strategy, quadratic equations in modular arithmetic can always be reduced to `square root' questions. As we saw above, sometimes these square roots exist, and sometimes they don't. Our goal now is to understand when square roots exist in modular arithmetic.
By the Chinese remainder theorem and a tool called Hensel's lemma, which we explore more in the article Using calculus to do number theory, studying square roots in modular arithmetic more or less boils down to understanding square roots modulo prime numbers.
So for the rest of this article, we focus on the following question: when is an integer \(a\) congruent to a perfect square modulo a prime number \(p\)?
For example, when \(p = 7,\) the residues \(0, 1, 2,\) and \(4\) are all perfect squares: \[0^2 \equiv 0 \pmod{7},\] \[1^2 \equiv 6^2 \equiv 1 \pmod{7},\] \[2^2 \equiv 5^2 \equiv 4 \pmod{7},\] and \[3^2 \equiv 4^2 \equiv 2 \pmod{7}.\] There are no other numbers we can square modulo 7 besides \(0, 1, 2, 3, 4, 5,\) and \(6,\) so the only perfect squares modulo 7 are the numbers \(0, 1, 2, 4\) we get as outputs.
Similarly, by squaring every possible residue, it's possible to compute the list of all perfect squares modulo a prime \(p.\) Below, you can ask your computer to do this procedure; it will list all the nonzero perfect squares for you, and also all the non-zero squares. We note though that the below table of residues doesn't include 0, which is always a square!
| Squares mod p |
|---|
| Non-squares mod p |
What do you notice from these tables? Maybe the first thing you saw was that there are always the same number of nonzero perfect squares as there are non-squares. Why could that be true?
Recall that, when we were finding all the squares modulo 7, we found that square roots came in pairs: \[1^2 \equiv 6^2 \equiv 1 \pmod{7},\] \[2^2 \equiv 5^2 \equiv 4 \pmod{7},\] and \[3^2 \equiv 4^2 \equiv 2 \pmod{7}.\]
This is analogous to the fact that, over the real numbers, \(a^2 = (-a)^2.\) In modular arithmetic, the corresponding fact is that \(a^2 \equiv (p-a)^2 \pmod{p}.\) So, for example, when \(p = 7,\) we find that \(1\) and \(7-1=6\) both have the same square; and \(2\) and \(7-2=5\) have the same square; and \(3\) and \(7-3=4\) have the same square.
Thus, to find all the squares modulo \(p,\) we don't need to square every residue from \(0\) to \(p-1.\) We just need to compute \[0^2, 1^2, 2^2, ..., \left(\frac{p-1}{2}\right)^2.\] By stopping halfway, we never miss any squares, because any of the bigger numbers have the same square as a smaller number, thanks to this \(a^2 \equiv (p-a)^2\pmod{p}\) trick. This tells us that there are exactly \(\frac{p+1}{2}\) perfect squares and \(\frac{p-1}{2}\) non-squares modulo \(p.\)
While this observation is interesting, it doesn't seem to reveal much else on which numbers are squares modulo \(p.\) However, Legendre had an amazing insight on this question: above, we chose a prime \(p\) and listed all the squares; instead, let's fix an integer \(a,\) and ask for which primes \(p\) the integer \(a\) is a perfect square. Try playing with the following table, and see what patterns you notice.
| p |
|---|
| a is a square mod p? |
After spending a long time with these tables, Legendre found a sneaky pattern. To illustrate his pattern, let's add one more row to these tables...
| p |
|---|
Legendre observed an amazing pattern:
So, Legendre observed that the primes \(p\) such that \(a\) is a square modulo \(p\) only depend on the residue of \(p\) modulo some other number! Moreover, in this example of \(p=5,\) note that \(5\) is a perfect square modulo \(p\) exactly when \(p\) is a perfect square modulo \(5.\)
To formalize his laws, Legendre introduced the quadratic residue symbol. The definition is very simple: \[\left(\frac{a}{p}\right) := \begin{cases} 0 & \text{ if \(a\) is divisible by \(p\),} \\ 1 & \text{ if \(a\) is a perfect square modulo \(p\) (and not divisible by \(p\)),} \\ -1 & \text{ if \(a\) is not a perfect square modulo \(p\).}\end{cases}\] For example, \[\left(\frac{3}{23}\right) = +1,\] because \(3\) is a perfect square modulo 23 (note \(7^2 \equiv 3\pmod{23}\)).
We can now state Legendre's observations as follows. The first supplementary law asserts that, for any odd prime \(p,\) \[\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & p \equiv 1\pmod{4}, \\ -1 & p \equiv 3\pmod{4}.\end{cases}\] The second supplementary law asserts that, for any odd prime \(p,\) \[\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 & p \equiv 1, 7 \pmod{8}, \\ -1 & p \equiv 3, 5\pmod{8}.\end{cases}\] These first and second supplementary laws encode what Legendre observed when looking at \(a = -1\) and \(a = 2\) in the tables above.
Legendre's general observation is called Gauss's law of quadratic reciprocity, and it asserts that for any distinct odd primes \(p, q\), \[\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \cdot \left(\frac{q}{p}\right).\]
For example, when \(q = 5,\) quadratic reciprocity states \[\left(\frac{p}{5}\right) = \left(\frac{5}{p}\right),\] because the sign becomes \[(-1)^{\frac{p-1}{2} \cdot \frac{5-1}{2}} = (-1)^{\frac{p-1}{2} \cdot 2} = 1,\] as \(-1\) raised to an even power is always \(+1.\) This is exactly the observation Legendre made about when \(5\) is a square modulo \(p\): \((5/p) = (p/5),\) so \(5\) is a square modulo \(p\) if and only if \(p\) is a square modulo \(5.\)
You might wonder how Gauss got involved. The answer is that, while Legendre conjectured the law of quadratic reciprocity -- and even got very close to a proof! -- Gauss was ultimately the person to prove quadratic reciprocity, and explain why it held (instead of simply observing it held in different examples). Gauss proved quadratic reciprocity in his famous book Disquisitiones Arithmeticae, in which he also laid the foundations of modern number theory. The law of quadratic reciprocity is named after Gauss in honor of his contributions towards it.
Gauss' law of quadratic reciprocity can be used to give a quick algorithm for deciding whether a number \(a\) is a square modulo a prime number \(p.\) Before giving this algorithm, we observe the following fundamental identity: \[ \bigg(\frac{ab}p\bigg)=\bigg(\frac ap\bigg)\bigg(\frac bp\bigg). \]
For example this says that if \(a\) and \(b\) are squares modulo \(p\) then \[ \bigg(\frac{ab}p\bigg)=1\cdot1=1 \] so \(ab\) is also a square modulo \(p\). Of course we expect this, since if \(a=s^2\) and \(b=t^2\) then \(ab=(st)^2\) is still a square. Less obviously (but nevertheless still true!) is the fact that if neither \(a\) nor \(b\) are squares modulo \(p\) then \(ab\) must be a square, since \[ \bigg(\frac{ab}p\bigg)=(-1)\cdot(-1)=1. \] For example, earlier we saw \(3\) and \(6\) are not squares modulo \(7\), and hence \(3\cdot6\equiv4\pmod{7}\) must be a square modulo \(7\)!
With this additional observation, let us answer: is \(463\) a square modulo \(1031\)? First, since both \(463\) and \(1031\) are prime, we can use quadratic reciprocity to see \[ \bigg(\frac{463}{1031}\bigg)=-\bigg(\frac{1031}{463}\bigg). \]
But since \(1031\equiv105\pmod{463}\) this is just equal to \(\big(\frac{105}{463}\big)\). Now \(105\) factorizes as \(3\cdot5\cdot7\), so by the multiplicativity of quadratic residues, \[ -\bigg(\frac{105}{463}\bigg)=-\bigg(\frac3{463}\bigg)\bigg(\frac5{463}\bigg)\bigg(\frac7{463}\bigg). \]
Now we can use quadratic reciprocity on each of these factors: \[ \begin{align*} \bigg(\frac3{463}\bigg)&=-\bigg(\frac{463}3\bigg)=-\bigg(\frac13\bigg)=-1, \\ \bigg(\frac5{463}\bigg)&=\bigg(\frac{463}5\bigg)=\bigg(\frac35\bigg)=-1, \\ \bigg(\frac7{463}\bigg)&=-\bigg(\frac{463}7\bigg)=-\bigg(\frac17\bigg)=-1. \end{align*} \] Combining everything, we see \[ \bigg(\frac{463}{1031}\bigg)=-\bigg(\frac3{463}\bigg)\bigg(\frac5{463}\bigg)\bigg(\frac7{463}\bigg)=-(-1)(-1)(-1)=1, \] so \(463\) is a square modulo \(1031\)! In fact, even though we now know \(463\) is a square, we have no idea what it's square root is (it turns out to be \(325\)).
Today we explored solutions to quadratic equations in modular arithmetic. What if we instead look at cubic equations, such as \(x^3-x-1 \equiv 0\pmod{p}\)? By trying every residue with a calculator, you can check \(x^3-x-1\equiv0\pmod p\) has a solution when \[ p=5,7,11,17,19,23,37,43,53,59,61,\cdots \] and doesn't have a solution when \[ p=2,3,13,29,31,41,47,71,73,\cdots \]
Unlike quadratic reciprocity, there is no clear pattern here. It turns out that there is a pattern, but it is highly non-obvious. The function \[ f(q)=q\prod_{n=1}^\infty(1-q^n)(1-q^{23n}) \] has the power series expansion \[ f(q)=q - q^2 - q^3 + q^6 + q^8 - q^{13} - q^{16} + q^{23} - \cdots \] It turns out that \(x^3-x-1\equiv0\pmod p\) has a solution exactly when the coefficient of \(q^p\) is \(0\) or \(+2\), and has no solution when the coefficient is \(-1\). The Langlands program generally predicts such a connection between the existence of solutions to polynomials mod \(p\) and coefficients of certain exotic functions, called modular forms.
As an aside, you might have noticed that our \(f(q)\) only seems to have coefficients which are 0, 1, or \(-1.\) So why did we say sometimes \(q^p\) could be \(+2\)? The reason is that the \(+2\)'s do appear, but only if you go very far out... here are the first hundred or so terms of \(f\): \[ \begin{align*} f(q) &= q - q^2 - q^3 + q^6 + q^8 - q^{13} - q^{16} + q^{23} \\ &-q^{24} + q^{25} + q^{26} + q^{27} - q^{29} - q^{31} + q^{39} \\ &-q^{41} - q^{46} - q^{47} + q^{48} + q^{49} - q^{50} - q^{54} \\ &+ q^{58} + 2q^{59} +q^{62} + q^{64} - q^{69} - q^{71} - q^{73} \\ &- q^{75} - q^{78} - q^{81}+q^{82} + q^{87} + q^{93} + q^{94} \\ &- q^{98} + 2q^{101} - q^{104} - 2q^{118}. \end{align*} \] You might notice from this larger expansion that \(q^{23}\) has coefficient 1, which isn't \(0, 2,\) or \(-1.\) It turns out \(23\) behaves a little strangely, because of a phenomena called ramification, which appears often in the theory of Diophantine equations. Ramification usually screws up patterns in number theory, but only for a finite number of exceptions; and the exceptions can all be found with some computation.