📂Number Theory

Proof of Gauss's Law of Quadratic Reciprocity

Theorem ¹

For two different 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) are different expressions of the same statement.

The theorem on quadratic residues is so cleanly organized that, aside from its utility, its mathematical beauty is exceptional. Gauss was the first to prove this and he valued this law so much that he left eight different proofs over his lifetime.

Proof

Strategy: In this post, we will introduce a proof that, although a bit long and not very sophisticated, doesn’t use difficult concepts. The core idea is Gauss’s amazing insight, and before we get into the formal proof, let’s take a quick look.

Gauss’s Idea: For primes $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}$ is satisfied, then $$a^{{p-1} \over {2} } = a^{n} \equiv e_{1} e_{2} \cdots e_{n} \pmod{p}$$

For example, if we look at the case of $a = 3$ being a quadratic residue in $\pmod{11}$, since $11 = 2n + 1 = 2 \cdot 5 +1$, we have $n=5$. Let’s calculate $3^{5} 5!$ directly. $$\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!$ gives us $3^{5} \equiv (-1)^2 \equiv 1 \pmod{11}$. What’s remarkable about this idea is that it turns the tedious process of raising to the power $a$ and dividing by $p$ into a 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}$

This means we can use Euler’s criterion more comfortably. In the example above, $$3^{{11- 1 } \over {2}} = 3^5 \equiv 1 \pmod{11}$$ Raising to a power and dividing by $p$ to find the remainder turns into a very simple problem.