📂Number Theory

Proof of Gauss's Law of Quadratic Reciprocity

Theorem ¹

For two distinct odd primes $p , q$, the following holds.

• (1): $$ \left( {{ q } \over { p }} \right) = \begin{cases} \left( {{ p } \over { q }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ p } \over { q }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• (2): $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

(1) and (2) differ only in expression but say the same thing.

It is so neatly organized in terms of quadratic residues that, quite apart from its utility, its mathematical beauty is exquisite. It is said that even after Gauss first proved it, he cherished this law so greatly that over his lifetime he left behind 8 different proofs.

Proof

Strategy: In this post I will introduce a proof that is a bit long and not very elegant, but that does not use difficult concepts. Gauss’s remarkable idea is the key, and before the proof proper let us briefly look into it.

Gauss’s idea: For a prime $p = 2n + 1$ and $1 \le x, x ' \le n$, if we set $e_{x} = \pm 1$ so that $ax \equiv e_{x} x ' \pmod{p}$ holds, then $$ a^{{p-1} \over {2} } = a^{n} \equiv e_{1} e_{2} \cdots e_{n} \pmod{p} $$

As an example, considering the case $a = 3$, which is a quadratic residue $\pmod{11}$, since $11 = 2n + 1 = 2 \cdot 5 +1$ we have $n=5$. Let us directly compute $3^{5} 5!$. $$ \begin{align*} 3^{5} 5! \equiv& (3 \cdot 1)(3 \cdot 2)(3 \cdot 3)(3 \cdot 4)(3 \cdot 1) \\ =& 3 \cdot 6 \cdot 9 \cdot 12 \cdot 15 \\ \equiv& 3 \cdot (-5) \cdot (-2) \cdot 1 \cdot 4 \pmod{11} \\ \equiv& (1 \cdot 3)(-1 \cdot 5)(-1 \cdot 2)(1 \cdot 1)(1 \cdot 4) \\ \equiv& (1 \cdot 1)(-1 \cdot 2)(1 \cdot 3)(1 \cdot 4)(-1 \cdot 5) \\ \equiv& (-1)^{2} 5! \pmod{11} \end{align*} $$ Dividing both sides by $5!$, we obtain $3^{5} \equiv (-1)^2 \equiv 1 \pmod{11}$. What is astonishing about this idea is that it allows us to turn the drudgery of raising $a$ to a power and dividing by $p$ into the problem of counting $(-1)$.

Euler’s criterion: For a prime $p \ne 2$, $\displaystyle a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p}$

In other words, this means that Euler’s criterion, which requires exponentiation, can be used far more conveniently. In the example above, $$ 3^{{11- 1 } \over {2}} = 3^5 \equiv 1 \pmod{11} $$ the drudgery of raising to a power, dividing by $p$, and finding the remainder became an exceedingly simple problem.

---

Let us set two primes $p,q$ as follows. $$ p := 2n +1 \\ q := 2m+1 $$ For $1 \le x,x’ \le n$ we have $q x \equiv e_{x} x ' \pmod{p}$, and by the definition of congruence, for some $y \in \mathbb{Z}$ we can set $$ qx = e_{x} x ' + py $$ as above. Since we are interested in counting $(-1)$, we only need to concern ourselves with the case $e_{x } = -1$. If $e_{x } = -1$, then $qx = -x’ + py$, and expressing it in terms of $y$, $$ y = {{1} \over {p}} (qx + x ' ) >0 $$ And since $\le x,x’ \le n$ and $2n < p$, $$ y = {{1} \over {p}} (qx + x ' ) \le {{(q+1)n} \over {p}} < {{q+1} \over {2}} = m+1 $$ Therefore $1 \le y \le m$. On the other hand, since by assumption $1 \le x , x ' \le n$, we have $1 \le x ' = py - qx \le n$. In other words, $e_{x} = -1$ means that there exists a $y$ satisfying $$ 1 \le x \le n \\ 1 \le y \le m \\ 1 \le py - qx \le n $$ Now, considering the following set $$ N : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le py - qx \le n \right\} $$ we have $$ \left( {{q} \over {p}} \right) \equiv q^{{p-1} \over {2}} = (-1 )^{|N|} \pmod{p} $$ Gauss’s idea turned exponentiation into the problem of counting $(-1)$, but we do not even intend to count that either, and for now we will just leave it as $|N|$ and move on. In the same manner as above, setting $$ M : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le qx - py \le m \right\} $$ we have $$ \left( {{p} \over {q}} \right) \equiv p^{{q-1} \over {2}} = (-1 )^{|M|} \pmod{q} $$ Here, since $$ |N| + |M| = | \left\{ (x,y) \ | \ 1 \le x \le n , 1 \le y \le m , -n \le qx - py \le m \right\} | $$ it follows that $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ holds. Now, let us take the set that shares no elements with $N$ $$ S = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , n < py - qx \right\} $$ and the set that shares no elements with $M$ $$ T : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , m < qx - py \right\} $$ If we define $f : S \to T $ by $$ f(x,y) = (x ' , y ' ) := (n + 1 - x , m + 1 -y) $$ then $$ \begin{align*} qx’ - py ' &= q(n + 1 - x) - p (m + 1 - y) \\ =& pn + q - qx - pm - p + py \\ =& (pn - pm ) + (p-q) - (qx - py) \end{align*} $$ Here, since $$ qn - pm = (2m+1)n - (2n+1)m = n - m \\ q-p = 2m + 1 - (2n+1) = 2(m-n) $$ we have $$ qx’ - py ' = n - m + 2m - 2n - (qx -py) =m-n-(qx - py) $$ Therefore $qx’ - py ' -m = -(qx - py + n) > 0$, that is, $qx’ - py ' > m$, and since $f$ is a bijection, $|S| = |T|$. Since the $N , M , S, T$ defined thus far share no elements with one another, $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ Now let us again compute $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ Since $|S| = |T|$, $$ (-1)^{|S| + |T|} = 1 \\ (-1)^{ |N| + |M| } = (-1)^{ |N| + |M| + |S| + |T| } $$ Here, since $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ it follows that $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{nm} $$ Since $p = 2n + 1$ and $q = 2m + 1$, $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

■

Meanwhile, the law of quadratic reciprocity can be generalized to odd numbers as follows by using the Jacobi symbol.

Generalization

For two distinct odd numbers $a , b$,

• [1]’: $$ \left( {{ b } \over { a }} \right) = \begin{cases} \left( {{ a } \over { b }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ a } \over { b }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• [2]’: $$ \left( {{ a } \over { b }} \right) \left( {{ b } \over { a }} \right) = (-1)^{ { {a-1} \over {2} }{ {b-1} \over {2} } } $$