Law of quadratic reciprocity

Statement

Let $p$ and $q$ be distinct odd primes. Then $$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}},$$ where the symbols are Legendre symbols.

Remarks

So $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ unless $p \equiv q \equiv 3 \pmod 4$. In that case $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$. For example, $\left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1$, and $3 \equiv 7 \equiv 3 \pmod 4$. So $\left(\frac{3}{7}\right) = -1$. With the first supplement, the second supplement and multiplicativity, the law computes every Legendre symbol.

History

Euler and Legendre conjectured the law. Gauss first proved it in 1796, and he published proofs in his Disquisitiones Arithmeticae of 1801. Gauss called it the fundamental theorem.

Explanations

L1 human

The law connects two questions: is $p$ a square modulo $q$, and is $q$ a square modulo $p$? The answers are the same, except when both primes leave remainder $3$ on division by $4$. Then the answers are opposite. This lets you swap and reduce the numbers, as in the Euclidean algorithm.