Quadratic Reciprocity

What is Quadratic Reciprocity?

The law of quadratic reciprocity is a well known number theoretic theorem that gives conditions for the solvability of quadratic equations modulo prime numbers.
Example: Are there solutions to the congruence $x^2 + 4x \equiv 10 \pmod{7}$?
Theorem: Let $p$ and $q$ be distinct odd primes. Then the law of quadratic reciprocity can be broken into three parts: $$\left( \frac{-1}{p} \right) = \begin{cases} 1 &p \equiv 1 \pmod{4} \\ -1 &p \equiv 3 \pmod{4} \end{cases}$$ $$\left( \frac{2}{p} \right) = \begin{cases} 1 &p \equiv 1 \rm\ or\ 7 \pmod{8} \\ -1 &p \equiv 3 \rm\ or\ 5 \pmod{8} \end{cases}$$ $$\left( \frac{q}{p} \right) = \begin{cases} \left( \frac{p}{q} \right) &p \equiv 1 \pmod{4} \text{ or } q \equiv 1 \pmod{4} \\ -\left( \frac{p}{q} \right) &p \equiv 3 \pmod{4} \text{ and } q \equiv 3 \pmod{4} \end{cases}$$ We will focus on the proof for the 3rd more general case for the purposes of this article.

Why is it Useful?

The main use for the law of quadratic reciprocity is to compute Legendre symbols.
Definition: The Legendre symbol of $a$ modulo $p$ is $$\left( \frac{a}{p} \right) = \begin{cases} 1 &\text{if a is a quadratic residue modulo p} \\ -1 &\text{if a is a nonresidue modulo p} \end{cases}$$ In essence, the Legendre symbol denotes whether a solution exists to the equation $x^2 \equiv a \pmod{p}$.
Example: $$\left( \frac{55}{179} \right) = \left( \frac{5}{179} \right) \cdot \left( \frac{11}{79} \right) = \left( \frac{179}{5} \right) \cdot -\left( \frac{179}{11} \right) = -\left( \frac{4}{5} \right) \cdot \left( \frac{3}{11} \right) \\ = -\left( \frac{3}{11} \right) = \left( \frac{11}{3} \right) = \left( \frac{2}{3} \right) = -1.$$ As you can see, the law of quadratic reciprocity allowed us to determine that $55$ is not square modulo $79$. At this point, one might be inclined to ask how to find the solutions given the result that a number is a quadratic residue. The answer to this problem is a separate matter (see Quadratic residues) and will not be discussed here.

Proof of the Theorem

There are actually many different proofs for quadratic reciprocity. We outline two of them below.

Eisenstein's Proof

Eisenstein's proof uses a criterion of Gauss that we will prove before discussing his argument.

Gauss's Criterion

Theorem: Let $p$ be and odd prime, let $a$ be an integer that is not divisible by $p$, and let $\mu(a, p) = $ the number of integers in the list $a, 2a, ..., Pa$ that become negative when the integers in the list are reduced modulo $p$ into the interval from $-P$ to $P$. Then $$\left( \frac{a}{p}\right) = (-1)^{\mu(a, p)}.$$ Before starting the proof of Gauss's Criterion, we first introduce a lemma that describes what happens when we reduce $a, 2a, 3a, ..., Pa$ modulo p.
Lemma: When the numbers $a, 2a , 3a , ... , Pa$ are reduced modulo p into the range from $-P$ to $P$, the reduced values are $\pm1, ..., \pm P$ in some order, with each number appearing once with either a plus sign or a minus sign.
We will not prove this lemma here, but hope it comes as a good exercise to the reader.
Proof of Gauss: We start by taking the list of numbers $a, 2a, ..., Pa$ and multiplying them. The product equals $$a \cdot 2a \cdot\cdot\cdot Pa = a^P(1 \cdot 2 \cdot\cdot\cdot P) = a^P \cdot P!. \tag{*}$$ On the other hand, the Lemma above tells us that $$a \cdot 2a \cdot\cdot\cdot Pa \equiv (\pm1)(\pm2)\cdot\cdot\cdot(\pm P) \pmod{p},$$ where the number of minus signs is $\mu(a, p)$ by definition. So $$\begin{align*} a \cdot 2a \cdot\cdot\cdot Pa &\equiv (-1)^{\mu(a, p)} \cdot 1 \cdot 2 \cdot\cdot\cdot P \pmod{P} \\ &\equiv (-1)^{\mu(a, p)} \cdot P! \pmod{P}. \tag{**} \end{align*}$$ Comparing the formula $(*)$ to the congruence $(**)$, we see that $$a^P \cdot P! \equiv (-1)^{\mu(a, p)} \cdot P!.$$ The number $P!$ is not divisible by $p$, so we may cancel it from both sides of the congruence to get $$a^P \equiv (-1)^{\mu(a, p)} \pmod{p}.$$ Finally, we observe that Euler's Criterion says that $$a^P \equiv \left( \frac{a}{p} \right) \pmod{p},$$ (remember that $P = \frac{p-1}{2}$), so $$\left( \frac{a}{p} \right) \equiv (-1)^{\mu(a, p)} \pmod{p}.$$ This says that $\left( \frac{a}{p} \right) - (-1)^{\mu(a, p)}$ is divisible by $p$. But the quantity $\left( \frac{a}{p} \right) - (-1)^{\mu(a, p)}$ equals either $-2, 0, \rm or, 2$, while $p \geq 3$, so we conclude that $\left( \frac{a}{p} \right) - (-1)^{\mu(a, p)} = 0. \square$

Rest of the proof coming soon.

A Journey Through Permutations

Before we get to the second proof of quadratic reciprocity, we are going to need to learn a little bit about algebraic permutations. A permutation of a set $S$ is defined as a bijection from $S$ to itself. That is, it is a function from $S$ to $S$ that is both injective (one-to-one) and surjective (onto). For example, $f: \{1, 2, 3, 4\} \to \{1, 2, 3, 4\}$ is a permutaion given by $$f(n) = \begin{cases} n+1 & n < 4 \\ 1 & n = 4 \end{cases}$$ It can be visualized as such:

Notice the cycle decomposition and $sgn()$ value accompanying the figure above.
Definition: The $\textit{cycle decomposition}$ is a quick way to write out a permutation without having to draw it or write out a piecewise function. It simply maps the current element to the subsequent one.
Example: The cycle decomposition $(1 3 2 4)$ refers to the permutation mapping $1 \to 3 \to 2 \to 4 \to 1$.
Definition: The $sgn()$ or sign of a permutation $p$ is defined as $$sgn(p) = \begin{cases} 1 &\text{if the number of crossings is even} \\ -1 &\text{if the number of crossings is odd} \end{cases}$$ or equivalently $sgn(p) = (-1)^{\text{# of inversions}}$ where an inversion is a pair $(i, j)$ such that $i < j$, but $p(i) > p(j)$.
Permutations can be composed just like normal functions. Say you have a permutation $\sigma$ and another permutation $\tau$. Then $\sigma \circ \tau = \sigma(\tau(n))$ and $\tau \circ \sigma = \tau(\sigma(n))$. Note that permutation groups are non-abelian, so $\sigma \circ \tau \neq \tau \circ \sigma$.

Try composing some permutations yourself below:

Other sign facts: $$sgn(\sigma\tau) = sign(\sigma) \cdot sign(\tau)$$ $$sgn(\text{m-length-cycle}) = (-1)^{m-1}$$

Matt Baker's Proof

Now with some basic knowledge of permutations, we are ready to tackle the proof that Dr. Matt Baker outlines in his blog here.

Zolotarev's Lemma

Definition: Let $\tau_a$ be the permutation of $\{1, 2, ..., p-1\}$ given by multiplying by $a$ modulo $p$ where $a$ is an integer not divisible by the odd prime $p$. Then Zolotarev's Lemma states $$ \left( \frac{a}{p} \right) = \left[ \frac{a}{p} \right]$$ where $\left[ \frac{a}{p} \right] = sgn(\tau_a)$.
Proof: Let $g$ be a primitive root modulo $p$ and let $k=\rm ind_g(a)$. As a set, $\{1, 2, ..., p-1\} = \{g^0, g^1, ..., g^{p-2}\}$ modulo $p$. This means multiplying by $a$ is equivalent to adding $k$ modulo $p-1$ on $\{0, 1, ..., p-2\}$. Therefore $$sgn(\tau_a) = ((-1)^{\frac{p-1}{(k, p-1)} - 1})^{(k, p-1)} = (-1)^{p-1-(k, p-1)} = (-1)^{(k, p-1)} \text{ since (p-1) is even.}$$ But, $$ (k, p-1) \text{ is } \begin{cases} \text{odd} &\text{if k is odd} \\ \text{even} &\text{if k is even} \end{cases}$$ and therefore, $$sgn(\tau_a) = (-1)^k = \left( \frac{a}{p} \right). \square$$

Now that we understand Zolotarev's Lemma, we can discuss the proof proposed by Matt Baker.
First, we need to define some permutaions in the form of playing card arrangements. Let $m$ and $n$ be odd relatively prime positive integers. We have a stack of $mn$ playing cards numbered $0$ through $mn-1$ and you want to deal them onto the table in an $m \times n$ rectangular array. Consider the following three ways of doing this:

Row Deal ($\rho$): Deal the cards into rows, going left to right and top to bottom.

Column Deal ($\kappa$): Deal the cards into columns, going top to bottom and left to right.

Diagonal Deal ($\delta$): Deal the cards diagonally down and to the right, wrapping around from bottom to top or right to left whenever necessary.

Additionally, each of these operations has an inverse action which undos the above deals. We will denote these by Row pickup ($\rho^{-1}$), Column pickup ($\kappa^{-1}$), and Diagonal pickup ($\delta^{-1}$). We combine these basic moves as follows, obtaining three different permutations of the rectangular array which we denote by $\alpha$, $\beta$, and $\gamma$:

$\alpha = \delta \circ \rho^{-1}$ is a row pickup followed by a diagonal deal.

$\beta = \delta \circ \kappa^{-1}$ is a column pickup followed by a diagonal deal.

$\gamma = \kappa \circ \rho^{-1}$ is a row pickup followed by a column deal.

Note that $\alpha$ permutes each column separately and $\beta$ permutes each row separately. Now, we can make a key observation.

Observation: $\alpha = \beta \circ \gamma$. Thus, $sgn(\alpha) = sgn(\beta) \cdot sgn(\gamma)$.
In fact, this self-evident observation is the Law of Quadratic Reciprocity in disguise! Here's an explanation.

Claim 1: $sgn(\alpha) = \left[ \frac{m}{n} \right]$ and $sgn(\beta) = \left[ \frac{n}{m} \right]$.

Claim 2: $sgn(\gamma) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$.

From these claims, we obtain:
Definition (Zolotarev’s Reciprocity Law): Let $m$ and $n$ be relatively prime odd positive integers, then $$\left[ \frac{n}{m} \right] = (-1)^{\frac{(m-1)(n-1)}{4}} \left[ \frac{m}{n} \right].$$ This law, used in conjuntion with Zolotarev's Lemma, gives us the law of quadratic reciprocity! All that's left to do is prove the two claims listed above.
For the explanation, it is helpful to identify the initial stack of cards with the set of integers $\{ 0,1,2,\ldots, mn-1 \}$. Also, by indexing the rows of the array by $0,1,\ldots,m-1$ and the columns by $0,1,\ldots,n-1$, we can identify the array with the set ${\mathbf Z}/m {\mathbf Z} \times {\mathbf Z}/n {\mathbf Z}$. In this way we can identify $\rho$, $\kappa$, and $\delta$ with the following maps from $\{ 0,1,2,\ldots, mn-1 \}$ to ${\mathbf Z}/m {\mathbf Z} \times {\mathbf Z}/n {\mathbf Z}$ (where $x \in \{ 0,1,\ldots,m-1 \}$ and $y \in \{ 0,1,\ldots,n-1 \})$: $$\rho(nx+y) = (x {\rm \; mod \;} m, y {\rm \; mod \;} n),$$ $$\kappa(x+my) = (x {\rm \; mod \;} m, y {\rm \; mod \;} n),$$ $$\delta(z) = (z {\rm \; mod \;} m, z {\rm \; mod \;} n).$$
Proof of Claim 1: By the above formulas we have $\alpha(x,y) = (nx+y,y)$ and $\beta(x,y) = (x,x+my)$. It follows that $\alpha$ is the product of the $n$ “column permutations” $\alpha_y(x) \mapsto nx+y \pmod{m}$. But each $\alpha_y$ is a composition of multiplication by $n$ modulo $m$ with the permutation $x \mapsto x+y \pmod{m}$, which always has sign $+1$ since it’s either trivial or a product of ${\rm GCD}(y,m)$ cycles, each of length $m/{\rm GCD}(y,m)$, and we’re assuming that $m$ is odd. Since $n$ is odd as well, we obtain the claim about ${\rm sign}(\alpha)$, and the corresponding assertion for $\beta$ follows by symmetry.

Proof of Claim 2: The sign of a permutation $\tau$ of a totally ordered finite set is equal to $-1$ to the number of inversions of $\tau$. We put the column-major order on our array. Note that for $a,b$ in the array, $\gamma(b)$ is less than $\gamma(a)$ in column-major order if and only if $b < a$ in row-major order. So $\{ a,b \}$ is an inversion pair in column-major order if and only if $a$ is below and to the left of $b$. The number of such inversion pairs is $\binom{m}{2} \cdot \binom{n}{2}$, since each pair of $2$-element subsets $\{ x,x' \}$ of $\{0,1,\ldots,m\}$ and $\{ y,y' \}$ of $\{0,1,\ldots,n\}$ gives rise to a unique inversion (by ordering the elements $a=(x,y),b=(x',y')$ so that $x < x'$ and $y' < y$). The claim follows since $m$ and $n$ are assumed to be odd.

And just like that, we reach the end of our long winded task to prove the Law of Quadratic Reciprocity.

Jacobi Symbols

This bonus section discusses Jacobi symbols, a generalization of Legendre symbols. Evaluating Legendre symbols is useful, but for large numbers, it is not feasible to factor the numerator and split into multiple Legendre symbols. This is where the Generalized Law of Quadratic Reciprocity comes in.
Theorem: Let $a$ and $b$ be odd positive integers. Then the generalized law of quadratic reciprocity can be broken into three parts: $$\left( \frac{-1}{b} \right) = \begin{cases} 1 &b \equiv 1 \pmod{4} \\ -1 &b \equiv 3 \pmod{4} \end{cases}$$ $$\left( \frac{2}{b} \right) = \begin{cases} 1 &b \equiv 1 \rm\ or\ 7 \pmod{8} \\ -1 &b \equiv 3 \rm\ or\ 5 \pmod{8} \end{cases}$$ $$\left( \frac{a}{b} \right) = \begin{cases} \left( \frac{b}{a} \right) &a \equiv 1 \pmod{4} \text{ or } b \equiv 1 \pmod{4} \\ -\left( \frac{b}{a} \right) &a \equiv 3 \pmod{4} \text{ and } b \equiv 3 \pmod{4} \end{cases}$$ As you may have noticed, this statement is extremely similar to the Law of Quadratic Reciprocity discussed above. In fact, the argument for Zolotarev's Lemma above generalizes to give quadratic reciprocity for the Jacobi symbol
Example: $$\left( \frac{55}{179} \right) = -\left( \frac{179}{55} \right) = -\left( \frac{14}{55} \right) = -\left( \frac{2}{55} \right) \cdot \left( \frac{7}{55} \right) = \left( \frac{55}{7} \right) = \left( \frac{6}{7} \right) \\ = \left( \frac{2}{7} \right) \cdot \left( \frac{3}{7} \right) = -\left( \frac{7}{3} \right) = -\left( \frac{1}{3} \right) = -1.$$ As you can see, we were able to evaluate the same Legendre as the beginning of the article without factoring $55$.