## Why is Quadratic Reciprocity so b-e-a-utiful?

This year I was able to do some tutorial teaching at uni. I was assigned a class of students doing the (extremely popular) course on Elementary Number Theory.

About halfway through the course the students learn about quadratic residues and quadratic reciprocity. However, when the students turned up to tutorials the beauty of these topics were not transfered. It is my opinion that not enough stress is put on the beauty of maths these days, there seems to be more emphasis on “doing it without care”.

Anyway, I thought i’d share my fascination with the Quadratic Reciprocity law.

We all know how to solve linear congruences, this is a simple task. There are either no solutions or $1$ solution (the case being decided by a comprimality check). When a solution exists, it is found by basically evaluating the inverse of something in a given group $(\mathbb{Z} / n\mathbb{Z})^{\times}$ and then multiplying through by it in the congruence.

If we step up the degree of the congruence by $1$ and start solving quadratic congruences the situation becomes much more complicated. All sorts of weird behaviour can happen. The fact that we have a quadratic does not mean that we have to have $0,1$ or $2$ roots anymore (examples of situations where there are more solutions are easy to come by).

This kind of behaviour is easily explained by using Hensel lifting and the Chinese Remainder Theorem. For this reason we look at cases where the modulus is prime (solving these lets us solve all other congruences where the modulus is composite).

Since $\mathbb{Z} / p\mathbb{Z}$ is a field, it does follow here that quadratic congruences mod $p$ will have $0,1$ or $2$ roots (so we are back in our comfort zone).

So let us take an arbitrary quadratic congruence $ax^2 + bx + c \equiv 0 \bmod p$, where $p$ is an odd prime number (the prime $2$ isnt really important here). Now we look at the usual way we solve quadratics. It is obvious that the quadratic formula is going to provide nothing here since this involves the square root function (which we have not defined mod $p$).

If the quadratic factorises into two linear factors with integer coefficients then by the dividing properties of prime numbers ($p|ab$ implies $p|a$ or $p|b$) we would then reduce to solving two linear congruences mod $p$, i.e. $a_1 x \equiv b_1 \bmod p$ and $a_2 x \equiv b_2 \bmod p$. Thus, here it is simple to find the solutions.

But what if it is difficult to spot a factorisation? Well in this case there is only one thing left to try, completing the square. Now most people complete the square in the usual fashion, i.e. divide the $x$ coefficient by $2$ etc. A way to do this without having to divide is to first multiply through by $4a$, where $a$ is the coefficient of the $x^2$ term. This way of completing the square will transfer over to quadratic congruences easily since we never had to divide.

So, multiplying through the quadratic congruence that we had above by $4a$ gives $4a^2 x^2 + 4abx + 4ac \equiv 0 \bmod p$, which can be written as $(2ax + b)^2 \equiv b^2 - 4ac \bmod p$.

From this, it is clear that we only need to solve equations of the form $y^2 \equiv m \bmod p$ since if we can solve these then the above would just lead to a set of linear congruences. The question arises, which $m$ give solutions? We call an $m$ such that $y^2 \equiv m \bmod p$ does have a solution a quadratic residue, and one that doesn’t is called a quadratic non-residue.

It turns out that there are nice patterns in the quadratic residues mod $p$. Also results on these things turn out to be extremely helpful when solving other Diophantine equations. For a basic example, if solving the Diophantine equation $x^2 + y^2 = 927097096901629619694703$, you might take a long time using what you know “pre-quadratic residues”, but using that fact that the quadratic residues mod $4$ are $0$ and $1$ we see that the value of $x^2 + y^2$ can only be $0,1$ or $2$ mod $4$. The huge number on the right is congruent to $3$ mod $4$, so there are no solutions!

We define the Legendre symbol to tell us when an integer $m$ is a “square number” mod $p$ (for odd prime $p$ and $m$ coprime to $p$). Given the $m$ and the $p$ above, we define this symbol to be $\left(\frac{m}{p}\right) = 1$ if $x^2 \equiv m \bmod p$ does have a solution (i.e. $m$ is a quadratic residue mod $p$) and $\left(\frac{m}{p}\right) = -1$ if not (i.e. $m$ is a quadratic non-residue mod $p$).

We made the restriction on $m$ since otherwise the congruence is the trivial one $x^2 \equiv 0 \bmod p$, which only admits one solution $x \equiv 0 \bmod p$. The point is that in all other cases we either get $2$ solutions or no solutions (it is easily seen that if $a^2 \equiv m \bmod p$ for some integer $a\in\{1,2,3,...,p-1\}$ then $(p-a)^2 \equiv m \bmod p$ so that the “square roots” mod $p$ are symmetrical).

For the algebraically minded, the Legendre symbol is just a group homomorphism $(\mathbb{Z}/p\mathbb{Z})^{\times} \longrightarrow \{1,-1\}$. It is what is known as a character of the group $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

The Legendre symbols has many nice properties, most of which are easy to prove. We have that $\left(\frac{k^2}{p}\right) = 1$ for all integers $k$ (coprime to $p$).

Also we have that $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ for all integers $a,b$ (coprime to $p$). This is the rule that makes the group homomorphism work, essentially saying that the product of two quadratic residues mod $p$ is another one, the product of two quadratic non-residues mod $p$ is a quadratic residue, and otherwise you get a quadratic non-residue.

Finally we have that we can “reduce the denominator” mod $p$. If $a \equiv b \bmod p$ then $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$.

Using these results, we can turn any Legendre symbol into a product of ones of the form $\left(\frac{-1}{p}\right), \left(\frac{2}{p}\right), \left(\frac{q}{p}\right)$ (where $q$ is a prime different from $p$).

I will not go into details here but the first of these two can be worked out using other methods of finding quadratic residues (Euler’s criterion and Gauss’ lemma). There are simple congruence conditions on $p$ that determine the values of these (we have that $\left(\frac{-1}{p}\right) = 1$ if and only if $p\equiv 1 \bmod 4$ and $\left(\frac{2}{p}\right) = 1$ if and only if $p\equiv 1, 7 \bmod 8$). But what about the last one? This is where the beauty of Quadratic Reciprocity comes in.

Quadratic Reciprocity gives us a way to turn the Legendre symbol $\left(\frac{q}{p}\right)$ into something about the Legendre symbol $\left(\frac{p}{q}\right)$. It is NOT an obvious thing that solutions to $x^2 \equiv q \bmod p$ and $x^2 \equiv p \bmod q$ are connected in any way, especially not in as simple a way as Quadratic Reciprocity proclaims.

This amazing theorem tells us that  if one or both of $p,q$ are congruent to $1 \bmod 4$ then we have that $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)$. If both are congruent to $3 \bmod 4$ then we simply add a minus sign, so that $\left(\frac{q}{p}\right) = -\left(\frac{p}{q}\right)$.

Why is this such a big help? Well one of $p,q$ is smaller than the other one, so working out the Legendre symbol could be a hard task by brute force. If we use Quadratic Reciprocity, we may simply flip the Legendre symbol and then reduce the now bigger numerator by the prime on the denominator. Then we may factorise the new numerator further and carry on using Quadratic Reciprocity until we reach a stage where the numbers are small enough to be able to calculate the answer.

Let’s see an example. Say we wanted to evaluate the Legendre symbol $\left(\frac{70}{199}\right)$, i.e. we want to know if $x^2 \equiv 70 \bmod 199$ has a solution. We may factorise 70 as $2\times 5\times 7$, then using the properties of the Legendre symbol we see that $\left(\frac{70}{199}\right) = \left(\frac{2}{199}\right) \left(\frac{5}{199}\right) \left(\frac{7}{199}\right) = \left(\frac{5}{199}\right) \left(\frac{7}{199}\right)$ since $199 \equiv 7 \bmod 8$. Now $5 \equiv 1 \bmod 4$ so we may “flip” the first Legendre symbol (this is by Quadratic Reciprocity). As for the second we have that both $7 = 3$ mod $4$ and $199$ $= 3$ mod $4$, so we may “flip” but have to add a minus sign infront.

So $\left(\frac{70}{199}\right) = -\left(\frac{199}{5}\right)\left(\frac{199}{7}\right) = -\left(\frac{4}{5}\right)\left(\frac{1}{7}\right) = -1$. In other words $x^2 \equiv 70 \bmod 199$ has no solution!

Quadratic Reciprocity has many proofs in many different complexities. The proof that is usually met first is one done by couting lattice points above and below a nicely chosen line. I have seen proofs using Algebraic Number Theory (which I may be able to provide in the future).

Also, it is nice to note what happens next. Is there a similar construction for “cubic residues”? Yes there is, there is a similar notion of Legendre symbol but now it takes values in the cube roots of unity (following suit with the group homomorphism/character stuff I mentioned earlier). Gauss studied these higher reciprocity laws (beyond cubic residues) and found that working with roots of unity gave the most appealing results.

These studies concluded with the more modern and complicated Artin Reciprocity law, which is a result of class field theory (a special branch of Algebraic Number Theory). It turns out that reciprocity laws really come from the number fields you are working in (with Quadratic Reciprocity we work with the base number field $\mathbb{Q}$, with Cubic Reciprocity we work with the cyclotomic number field $\mathbb{Q}(\zeta_3)$ where $\zeta_3$ is a primitive cube root of unity). Other non-cyclotomic number fields may give rise to extra reciprocity laws that arent counted in the Higher Reciprocity laws.

One of Hilbert’s famous problems asked for the most general Reciprocity law, one that works for all extensions of number fields. Artin’s law was a partial answer to this, it only worked in Abelian extensions (extensions with Abelian Galois group). There are still studies being made into the situation beyond these types of extension.