Introduction to Quadratic Reciprocity.


Introduction.

Despite having the "algebra" tag, quadratic reciprocity is generally considered a theorem in number theory. The application I'm most familiar with is with helping with solvability of quadratic equations modulo prime numbers.

What is Quadratic Reciprocity?

In order to talk about quadratic reciprocity, we need to talk about two central items in the theory: a quadratic residue and the Legendre Symbol.

Okay, What is a Quadratic Residue?

First, if you haven't seen modular arithmetic before, you might want to stop and check that out. After you have that under your hat, let's ask ourselves the following concrete question: if we think of the numbers $\{0,1,2,3,4\}$ under mod 5 addition and multiplication , which we'll refer to as ${\mathbb Z}_{5}^{\times}$, then we can ask the following innocent-sounding question: what do square roots look like in ${\mathbb Z}_{5}^{\times}$?

Square roots can be defined in the following way: $a$ is the square root of $b$ if $a^2 = b$. Easy enough. What can we say about square roots in ${\mathbb Z}_{5}^{\times}$? Well, let's make a list. \begin{align} 0^2 & = 0\mod 5 = 0\\ 1^2 & = 1\mod 5 = 1 \\ 2^2 & = 4\mod 5 = 4 \\ 3^2 & = 9\mod 5 = 4 \\ 4^2 & = 16\mod 5 = 1 \end{align} What does this mean? It means that in ${\mathbb Z}_{5}^{\times}$ the only numbers that have square roots are 0, 1, and 4. The square root of 0 is 0, the square root of 1 is both 1 and 4, and the square root of 4 is 2 and 3. Kind of strange, right? But that's how it works in ${\mathbb Z}_{5}^{\times}$.

In general, if we look at any odd prime $p$, we can make ${\mathbb Z}_{p}^{\times}$ in the same way as we did for 5. For example, ${\mathbb Z}_{11}^{\times}$ has the elements $\{0,1,2,3,4,5,6,7,8,9,10\}$. Same kind of addition, same kind of multiplication.

Definition: Quadratic Residue mod $p$.

For $p$ an odd prime and $a$ an element in ${\mathbb Z}_{p}^{\times}$, we call $a$ a $\textit{quadratic residue}$ mod $p$ if there exists an element $b$ in ${\mathbb Z}_{p}^{\times}$ such that $b^2 = a$. If $a$ is not a quadratic residue, it is called a quadratic non-residue.

Quadratic residues can be thought of as a kind of perfect square in ${\mathbb Z}_{p}^{\times}$. In our example above with ${\mathbb Z}_{5}^{\times}$ the quadratic residues mod 5 are $0,1,4$. What about for ${\mathbb Z_{11}}^{\times}$?

Some (naive) Python code to find quadratic residues mod $p$ is given by the following:


def find_quad_residues(p):
	return set(pow(i,2,p) for i in range(p))

This simply brute-forces through every possibility and returns a set which allows us to kill off the duplicate values.

Great, Now What is the Legendre Symbol?

The Legendre symbol is denoted by the symbol $(\frac{a}{p})$ and is defined as follows, in a slightly cryptic way:

Definition: The Legendre Symbol.

Given an integer $a$ and an odd prime $p$, the Legendre Symbol is defined as follows. \[\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } a = 0 \text{ mod }p\\ 1 & \text{if } a \text{ is a quadratic residue mod } p\\ -1 & \text{if } a \text{ is a quadratic non-residue mod } p \\ \end{cases}\]

For example, we can evalue these for $p = 5$ from above. \[\begin{align} \left(\frac{0}{5}\right) & = 0\\ \left(\frac{1}{5}\right) & = 1\\ \left(\frac{2}{5}\right) & = -1\\ \left(\frac{3}{5}\right) & = -1\\ \left(\frac{4}{5}\right) & = 1 \end{align}\] Neato. Note that if we continued, our values would start to repeat since we are working modulo 5. The Legendre Symbol is a nice, easy way of telling us at a quick glance what is and what isn't a quadratic residue mod $p$. Now that we have these, let's discuss them a bit and talk about a few important properties that these numbers have.

Theorem.

Given an odd prime $p$ and an integer $a$, we have the following properties.

  1. $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$ if $a = b\mod(p)$.
  2. $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.
  3. If $a$ is coprime to $p$ then $\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}}\mod(p)$.
  4. In particular, $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$.
  5. $\left(\frac{2}{p}\right) = (-1)^{\frac{p^{2} - 1}{8}}$.

Properties 1 and 2 are left as exercises for the reader. Property 3 is called Euler's Criterion and I'm not going to prove it here but I encourage the curious reader to page through the proof; it's relatively straight-forward, just takes a bit of thinking. Property 4 is a direct consequence of Property 3, as in ${\mathbb Z}_{p}^{\times}$ the value -1 is equivalent to $p-1$ (why?), so this reduces to the question "When is $p-1$ relatively prime to $p$?". Since this is always the case besides when $p > 2$, it holds for each odd prime. Property 5 is a bit more mysterious, but it crops up so much that I included it in this list; I won't prove it here.

What about Quadratic Reciprocity?

Okay, now the big guns. Here's the theorem.

Theorem: Quadratic Reciprocity.

Given $p, q$ odd primes, \[\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{q}{p}\right).\]

We won't prove this theorem, but it is possible to prove this using Euler's Criterion above with a little extra work.

So what?

It might be a little mysterious why Quadratic Reciprocity is useful at this point. It seems to be an extremely narrow theorem because $p$ and $q$ are required to be different odd primes. But this turns out not to be so bad, since we can prime factorize and use some of the other properties above. Let's do an example to get a handle on this.

Example.

Let's find $\left(\frac{3345}{201}\right)$. Notice that $3345$ is not a prime number. In particular, $3345 = 3\cdot 5 223$. By the multiplicative property above, we have that \[\begin{align} \left(\frac{3345}{201}\right) = \left(\frac{3}{201}\right)\left(\frac{5}{201}\right)\left(\frac{213}{201}\right) \end{align}\] Which splits up the problem significantly. Notice that, by the first property, $\left(\frac{3345}{201}\right) = \left(\frac{12}{201}\right)$. But $10 = 2^{2}*3$ and so we may reduced the original expression to \[\begin{align} \left(\frac{3165}{201}\right) = \left(\frac{3}{201}\right)^{2}\left(\frac{5}{201}\right)\left(\frac{2}{201}\right)^{3} \end{align}\] Notice that any Legendre symbol which is squared (which is not 0) is equal to 1, so we may reduce all squares at this point. \[\begin{align} \left(\frac{3165}{201}\right) = \left(\frac{5}{201}\right)\left(\frac{2}{201}\right) \end{align}\] Let's just look at the first factor. Notice, by quadratic reciprocity, that \[\begin{align} \left(\frac{5}{201}\right) &= (-1)^{\frac{5-1}{2}\frac{201-1}{2}}\left(\frac{201}{5}\right)\\ &= \left(\frac{201}{5}\right) = \left(\frac{1}{5}\right)\\ &= 1 \end{align}\] Well, that took care of that pretty fast. We now have the much more simple \[\left(\frac{3165}{201}\right) = \left(\frac{2}{201}\right)\] We can't use quadratic reciprocity here (alas!) because 2 is not an odd prime. We use property 5 above to note that it is equal to $(-1)^{5050} = 1$, so we have that \[\left(\frac{3165}{201}\right) = 1\] Giving us that, in fact, 3016 is a quadratic residue mod 201. Amazing!

The astute reader will note that this is not too incredible; if we had simply reduced the first Legrange symbol we would have noted that \[\left(\frac{3165}{201}\right) = \left(\frac{1}{201}\right) = 1.\] Ugh. But this does not always happen and it is often the case that these numbers are nontrivial to solve for.

Example.

One more example. Let's quickly do $\left(\frac{43}{71}\right)$. Note that we can apply quadratic reciprocity here. \[\begin{align} \left(\frac{43}{71}\right) &= \left(\frac{71}{43}\right) = \left(\frac{28}{43}\right)\\ &= \left(\frac{2}{43}\right)^{2}\left(\frac{7}{43}\right) = \left(\frac{7}{43}\right)\\ \end{align}\] and we can apply quadratic reciprocity again here, \[\begin{align} \left(\frac{7}{43}\right) &= \left(\frac{43}{7}\right)\\ &= \left(\frac{1}{43}\right)\\ &= 1 \end{align}\] Which gives us that, in fact, 43 is a quadratic residue modulo 71. This is not entirely trivial to do with pencil and paper, but because these are small numbers we can do this with our python program to check to see that it is the case. Indeed, $43 = 16^2\mod(71)$.

Some Pretty Pictures.

Below is a graph of all of the quadratic residues mod $p$ for $p \lt 100$. It's kind of beautiful.

Homework.

  1. Is 360 is a quadratic residue mod 773?
  2. Read up on the uses of quadratic reciprocity.