Quadratic Reciprocity

Legendre symbols, Euler's criterion, and Gauss's reciprocity law.

The idea

Law of quadratic reciprocity. For distinct odd primes $p$ and $q$, $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}},$ where $\left(\frac{a}{p}\right)$ is the Legendre symbol: $+1$ when $a$ is a nonzero square modulo $p$ and $-1$ when it is not.

The exponent depends only on the primes modulo $4$. Each factor $\frac{p-1}{2}$, $\frac{q-1}{2}$ is odd exactly when its prime is congruent to $3$ modulo $4$, so the product is odd only when both primes are. In that one case the two symbols are opposite; in every other case they are equal.

The law relates two different moduli: whether $q$ is a square modulo $p$ determines whether $p$ is a square modulo $q$. It is also the practical method for evaluating a symbol. Flipping trades the modulus for a smaller prime, reducing the top modulo that prime shrinks the symbol again, and repeating brings it down to a value we can read off with no exponentiation at all.

Ways to work on it

• Walkthrough. State the law of quadratic reciprocity and see what it says about pairs of primes.
• Practice. Decide if a number is a quadratic residue mod a prime.
• Hardest. Evaluate a Legendre symbol with the reciprocity law.

Not sure where to start? Take the ten-question placement test.