Quadratic Residues and Reciprocity — Mathematics Knowledge System

Overview

A quadratic residue modulo a prime $p$ is an integer that is congruent to a perfect square mod $p$. The Law of Quadratic Reciprocity — called by Gauss the 'golden theorem' — gives a beautifully symmetric criterion for when an odd prime is a square mod another odd prime.

Intuition

Is $-1$ a square mod 13? Squares mod 13 are $1,4,9,3,12,10$ — yes, $5^2 = 25 \equiv 12 \equiv -1$. Quadratic reciprocity says: asking 'is $p$ a square mod $q$?' and 'is $q$ a square mod $p$?' have answers that are tightly linked — they agree unless both primes are $3 \pmod 4$.

Formal Definition

Definition

Let $p$ be an odd prime and $a \not\equiv 0 \pmod{p}$.

\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a QR mod } p \\ -1 & \text{if } a \text{ is a QNR mod } p \end{cases}

Legendre symbol

legendre

\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}

Euler's criterion for quadratic residues

euler-criterion

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}

Law of Quadratic Reciprocity (p, q distinct odd primes)

reciprocity

\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & p \equiv 1 \pmod{4} \\ -1 & p \equiv 3 \pmod{4} \end{cases}

First supplement

minus-one

\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}

Second supplement

two-supplement

Notation

Notation	Meaning
$\left(\frac{a}{p}\right)$	Legendre symbol: +1 if a is a QR mod p, -1 if QNR, 0 if p\|a
$\left(\frac{a}{n}\right)$	Jacobi symbol: product of Legendre symbols over prime factors of n

Theorems

Theorem 1: 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}}. Equivalently, \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right) unless p \equiv q \equiv 3 \pmod{4}, in which case they are negatives of each other.

Theorem 2: Counting Quadratic Residues

For an odd prime p there are exactly (p-1)/2 quadratic residues and (p-1)/2 quadratic non-residues in (\mathbb{Z}/p\mathbb{Z})^\times.

Worked Examples

Apply quadratic reciprocity. Both 137 and 331 are odd primes. Check $137 \equiv 1 \pmod 4$, so the reciprocity sign factor is $(-1)^{\frac{136}{2}\cdot\frac{330}{2}} = (-1)^{68 \cdot 165}$ — even exponent, so $\left(\frac{137}{331}\right) = \left(\frac{331}{137}\right)$.
$\left(\frac{137}{331}\right) = \left(\frac{331}{137}\right)$
$331 = 2 \cdot 137 + 57$, so $331 \equiv 57 \pmod{137}$. Thus $\left(\frac{331}{137}\right) = \left(\frac{57}{137}\right) = \left(\frac{3}{137}\right)\left(\frac{19}{137}\right)$.
$137 \equiv 1 \pmod 4$ and $3 \equiv 3 \pmod 4$: $\left(\frac{3}{137}\right) = \left(\frac{137}{3}\right) = \left(\frac{2}{3}\right) = -1$. Similarly, $137 \equiv 4 \pmod{19}$ so $\left(\frac{137}{19}\right) = \left(\frac{4}{19}\right) = 1$, giving $\left(\frac{19}{137}\right) = 1$. Product: $-1 \cdot 1 = -1$.

Answer: $\left(\frac{137}{331}\right) = -1$; 137 is a quadratic non-residue mod 331.

Practice Problems

Difficulty 6/10

Compute $\left(\frac{3}{7}\right)$.

Difficulty 7/10

For which primes $p > 2$ is 5 a quadratic residue mod $p$?

Difficulty 8/10

Prove Euler's criterion: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p$.

Historical Background

Euler observed the reciprocity phenomenon empirically; Legendre formulated it and gave an incomplete proof. Gauss published the first complete proof in 1796 and subsequently gave six more proofs. The law has since accumulated over 200 published proofs and sits at the heart of algebraic number theory and class field theory.

1748
Euler observes patterns in quadratic residues
Leonhard Euler
1785
Legendre states the law and introduces the Legendre symbol
Adrien-Marie Legendre
1796
Gauss gives the first complete proof (age 19)
Carl Friedrich Gauss

Summary

A quadratic residue mod $p$ is an $a$ with $x^2 \equiv a \pmod p$ solvable; there are $(p-1)/2$ of each type.
The Legendre symbol $\left(\frac{a}{p}\right) \in \{-1, 0, 1\}$ encodes residuosity.
Euler's criterion: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p$.
Quadratic Reciprocity: $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.
Supplements: $\left(\frac{-1}{p}\right) = 1 \iff p \equiv 1 \pmod 4$; $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$.

References

BookIreland, K. & Rosen, M. A Classical Introduction to Modern Number Theory. Springer, 1990.