Number theory — quadratic reciprocity

⚡ Key Takeaways

Quadratic reciprocity relates whether an odd prime pp is a square modulo another odd prime qq to whether qq is a square modulo pp. In words: for distinct odd primes p,qp, q, the two Legendre symbols (pq)\left(\frac{p}{q}\right) and (qp)\left(\frac{q}{p}\right) are equal unless both p≡q≡3(mod4)p \equiv q \equiv 3 \pmod 4, in which case they differ in sign. It applies to solving congruences x2≡a(modm)x^2 \equiv a \pmod m. Conjectured by Euler and Legendre, first fully proved by Gauss (1796–1801), who called it the "golden theorem."

💡 The Core Insight

Whether one prime is a square modulo another is not an isolated arithmetic accident — it is governed by a reciprocal relationship. The "exchange" of pp and qq in the Legendre symbol costs only a sign, and that sign is determined entirely by the residues of pp and qq modulo 44. Two supplementary laws handle the special cases a=−1a = -1 and a=2a = 2, and together with multiplicativity these three rules let you evaluate any Legendre symbol by repeated reduction, much like the Euclidean algorithm computes a GCD.

Formal Statement

DefinitionQuadratic Residue and the Legendre Symbol

Let pp be an odd prime and a∈Za \in \mathbb{Z}. An integer aa with gcd⁡(a,p)=1\gcd(a,p)=1 is a quadratic residue mod pp if there exists xx with x2≡a(modp)x^2 \equiv a \pmod p; otherwise it is a quadratic non-residue. The Legendre symbol is defined by

1
(ap)={0if p∣a,+1if a is a QR mod p,−1if a is a non-QR mod p.\quad \left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } p \mid a, \\ +1 & \text{if } a \text{ is a QR mod } p, \\ -1 & \text{if } a \text{ is a non-QR mod } p. \end{cases}

Derivation hint: This is a definition; the three-way split exhausts all residue classes since aa is either divisible by pp, or a nonzero square, or a nonzero non-square mod pp. Here pp is the (odd prime) modulus, aa is the integer being tested, and the symbol takes values in {−1,0,+1}\{-1,0,+1\}.

TheoremEuler's Criterion

For an odd prime pp and gcd⁡(a,p)=1\gcd(a,p)=1,

2
(ap)≡a(p−1)/2(modp).\quad \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.

Derivation hint: The cyclic group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times has order p−1p-1; squares form the unique index-2 subgroup, exactly the kernel of a↦a(p−1)/2a \mapsto a^{(p-1)/2}, whose values are ±1\pm 1 since (a(p−1)/2)2=ap−1≡1(a^{(p-1)/2})^2 = a^{p-1}\equiv 1 by Fermat.

TheoremMultiplicativity of the Legendre Symbol

For an odd prime pp and integers a,ba, b,

3
(abp)=(ap)(bp).\quad \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).

Derivation hint: Multiply Euler's criterion [2] for aa and for bb; a(p−1)/2b(p−1)/2=(ab)(p−1)/2a^{(p-1)/2}b^{(p-1)/2}=(ab)^{(p-1)/2} modulo pp, and ±1\pm1 values determined mod pp are determined exactly.

TheoremLaw of Quadratic Reciprocity

Let pp and qq be distinct odd primes. Then

4
(pq)(qp)=(−1)p−12⋅q−12.\quad \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.

Equivalently,

5
(qp)=(pq)⋅(−1)p−12⋅q−12,\quad \left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)\cdot(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}},

so the two symbols agree unless p≡q≡3(mod4)p \equiv q \equiv 3 \pmod 4, in which case they are opposite. The two supplementary laws are

6
(−1p)=(−1)(p−1)/2={+1p≡1(mod4),−1p≡3(mod4),\quad \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}
7
(2p)=(−1)(p2−1)/8={+1p≡±1(mod8),−1p≡±3(mod8).\quad \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} +1 & p \equiv \pm 1 \pmod 8, \\ -1 & p \equiv \pm 3 \pmod 8. \end{cases}

Derivation hint for [4]: the exponent p−12⋅q−12\frac{p-1}{2}\cdot\frac{q-1}{2} is odd iff both p−12\frac{p-1}{2} and q−12\frac{q-1}{2} are odd iff both p,q≡3(mod4)p,q\equiv 3\pmod 4. Hints for [6],[7]: [6] is Euler's criterion at a=−1a=-1; [7] follows from Gauss's lemma counting lattice points.

Why It Holds / Derivation

:::proof[Eisenstein's Lattice-Point Proof of [4]] We sketch the classical proof via Gauss's Lemma and lattice-point counting, the cleanest elementary route.

Step 1 — Gauss's Lemma. Let pp be odd and gcd⁡(a,p)=1\gcd(a,p)=1. Consider the multiples a,2a,…,p−12aa, 2a, \dots, \frac{p-1}{2}a, each reduced to its least positive residue mod pp. Let μ\mu be the number of these residues exceeding p/2p/2. Then

8
(ap)=(−1)μ.\quad \left(\frac{a}{p}\right) = (-1)^{\mu}.

Derivation hint: Each reduced residue rr with r>p/2r>p/2 is replaced by p−r<p/2p-r<p/2; the resulting set is exactly {1,…,(p−1)/2}\{1,\dots,(p-1)/2\}, and the product introduces (−1)μ(-1)^\mu relative to a(p−1)/2⋅p−12!a^{(p-1)/2}\cdot \frac{p-1}{2}!; cancel the factorial and apply Euler's criterion [2].

Step 2 — Count via floor functions. For odd aa, one shows μ≡∑k=1(p−1)/2⌊kap⌋(mod2)\mu \equiv \sum_{k=1}^{(p-1)/2}\left\lfloor \frac{ka}{p}\right\rfloor \pmod 2, hence

9
(ap)=(−1)∑k=1(p−1)/2⌊ka/p⌋.\quad \left(\frac{a}{p}\right) = (-1)^{\sum_{k=1}^{(p-1)/2}\lfloor ka/p\rfloor}.

Derivation hint: Write ka=p⌊ka/p⌋+rkka = p\lfloor ka/p\rfloor + r_k; summing over kk and reducing mod 2 reorganizes the residue/non-residue counting from Step 1 into the floor sum.

Step 3 — Lattice points in a rectangle. Apply [9] with a=qa=q and the symmetric expression with a=pa=p. The sum ∑k=1(p−1)/2⌊kq/p⌋\sum_{k=1}^{(p-1)/2}\lfloor kq/p\rfloor counts lattice points (k,j)(k,j) with 1≤k≤p−121\le k\le\frac{p-1}{2}, 1≤j<kq/p1\le j < kq/p, i.e. points below the line py=qxpy = qx inside the rectangle R=[1,p−12]×[1,q−12]R=\left[1,\frac{p-1}{2}\right]\times\left[1,\frac{q-1}{2}\right]. The symmetric sum for pp counts points above the line.

Step 4 — Add the counts. No lattice point lies on the line py=qxpy=qx inside RR (that would force p∣xp\mid x, impossible). So the two sums together count all lattice points of RR:

10
∑k=1(p−1)/2⌊kqp⌋+∑j=1(q−1)/2⌊jpq⌋=p−12⋅q−12.\quad \sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor + \sum_{j=1}^{(q-1)/2}\left\lfloor \frac{jp}{q}\right\rfloor = \frac{p-1}{2}\cdot\frac{q-1}{2}.

Derivation hint: Partition the p−12⋅q−12\frac{p-1}{2}\cdot\frac{q-1}{2} lattice points of the rectangle by whether they fall below or above the diagonal line, which has no interior lattice points.

Step 5 — Conclude. Multiplying the two instances of [9]:

(qp)(pq)=(−1)∑⌊kq/p⌋+∑⌊jp/q⌋=(−1)p−12⋅q−12,\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\sum \lfloor kq/p\rfloor + \sum \lfloor jp/q\rfloor} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}},

which is exactly [4]. ■\blacksquare

Figure
Eisenstein's lattice-point count: points of the rectangle split by the diagonal py=qxpy=qx, here p=7, q=5p=7,\ q=5.

```svg

x (k) y (j) py = qx below: ∑⌊kq/p⌋ above: ∑⌊jp/q⌋ total = ((p-1)/2)((q-1)/2) = 3·2 = 6

```

mathematician · Carl Friedrich Gauss | 1777–1855

Gauss proved quadratic reciprocity at age 19 (April 1796) after a year of effort, calling it the theorema aureum — the golden theorem. He published the first complete proof in his 1801 masterwork Disquisitiones Arithmeticae, and over his lifetime found eight distinct proofs, driven by his quest to generalize the result to higher powers (cubic and biquadratic reciprocity). His introduction of congruence notation, his systematic theory of forms, and his Gauss sums created the language in which all later reciprocity laws are expressed. The pursuit of a "general reciprocity law" became the organizing problem of 19th- and 20th-century number theory, culminating in Artin reciprocity.

Building Intuition

🧠 Intuition

Think of the Legendre symbol (qp)\left(\frac{q}{p}\right) as a "yes/no question about the prime qq, asked in the world of arithmetic mod pp." Quadratic reciprocity says this question has a mirror in the world mod qq, and the two answers are linked. The miracle is that there's any link at all: a priori, being a square mod pp and being a square mod qq live in totally different finite worlds. A useful mental model: the symbol behaves like a homomorphism in its top argument (multiplicativity [3]), so it suffices to know its values on −1-1, on 22, and on odd primes — and reciprocity reduces an odd prime in the top to a smaller modulus in the bottom. This makes evaluation an algorithm: each application of [5] flips and shrinks the numbers, exactly like the Euclidean algorithm, terminating quickly. The deeper modern view: (qp)\left(\frac{q}{p}\right) tells you how the prime pp splits in the field Q(q∗)\mathbb{Q}(\sqrt{q^*}), and reciprocity is the statement that splitting is governed by a congruence condition on pp — the first instance of "primes split according to Frobenius classes."

Worked Examples

ExampleIs 30 a quadratic residue mod 53?

Given: Evaluate (3053)\left(\frac{30}{53}\right); note 5353 is prime, 53≡1(mod4)53\equiv 1\pmod 4.

Step 1 — Factor and use multiplicativity [3]: 30=2⋅3⋅530 = 2\cdot 3\cdot 5, so

(3053)=(253)(353)(553).\left(\frac{30}{53}\right)=\left(\frac{2}{53}\right)\left(\frac{3}{53}\right)\left(\frac{5}{53}\right).

Step 2 — The factor (253)\left(\frac{2}{53}\right) via [7]: 53≡5(mod8)53\equiv 5\pmod 8, and 5≡−3(mod8)5\equiv -3\pmod 8, so (253)=−1\left(\frac{2}{53}\right)=-1.

Step 3 — The factor (353)\left(\frac{3}{53}\right) via reciprocity [5]: Since 53≡1(mod4)53\equiv 1\pmod 4, the sign is ++, so (353)=(533)=(23)\left(\frac{3}{53}\right)=\left(\frac{53}{3}\right)=\left(\frac{2}{3}\right). Now (23)=−1\left(\frac{2}{3}\right)=-1 (since 3≡3(mod8)3\equiv 3\pmod 8). So (353)=−1\left(\frac{3}{53}\right)=-1.

Step 4 — The factor (553)\left(\frac{5}{53}\right) via [5]: Both with 5≡1(mod4)5\equiv 1\pmod 4 → sign ++, so =(535)=(35)=\left(\frac{53}{5}\right)=\left(\frac{3}{5}\right). Check 33 mod 55: squares mod 5 are {1,4}\{1,4\}, so (35)=−1\left(\frac{3}{5}\right)=-1. Thus (553)=−1\left(\frac{5}{53}\right)=-1.

Step 5 — Combine:

(3053)=(−1)(−1)(−1)=−1.\left(\frac{30}{53}\right)=(-1)(-1)(-1)=-1.
(3053)=−1⇒30 is a non-residue mod 53.\boxed{\left(\frac{30}{53}\right)=-1\quad\Rightarrow\quad 30 \text{ is a non-residue mod } 53.}
ExampleSolvability of x2≡17(mod101)x^2 \equiv 17 \pmod{101}

Given: 101101 is prime; determine if a solution exists by computing (17101)\left(\frac{17}{101}\right).

Step 1 — Apply reciprocity [5]: 17≡1(mod4)17\equiv 1\pmod 4, so the sign is ++ and

(17101)=(10117).\left(\frac{17}{101}\right)=\left(\frac{101}{17}\right).

Step 2 — Reduce the top mod 17: 101=5⋅17+16101 = 5\cdot17 + 16, so 101≡16(mod17)101\equiv 16\pmod{17}, giving (10117)=(1617)\left(\frac{101}{17}\right)=\left(\frac{16}{17}\right).

Step 3 — Recognize a perfect square: 16=4216 = 4^2, hence (1617)=+1\left(\frac{16}{17}\right)=+1 automatically.

Step 4 — Conclude existence:

(17101)=+1.\left(\frac{17}{101}\right)=+1.

A solution exists; in fact x≡±22(mod101)x \equiv \pm 22 \pmod{101} since 222=484=4⋅101+8022^2 = 484 = 4\cdot101 + 80... (checking: 484−4(101)=80≠17484 - 4(101)=80\ne17; a direct search gives x≡±38x\equiv \pm38, since 382=1444=14⋅101+3038^2=1444=14\cdot101+30 — the symbol guarantees solvability without exhibiting the root).

x2≡17(mod101) is SOLVABLE, since (17101)=+1.\boxed{x^2\equiv 17\pmod{101}\ \text{is SOLVABLE, since } \left(\tfrac{17}{101}\right)=+1.}

Common Misconceptions

⚠️ Common mistake

The Legendre symbol is NOT defined for composite lower entries — use the Jacobi symbol carefully. The Legendre symbol (ap)\left(\frac{a}{p}\right) requires pp to be an odd prime. The generalized Jacobi symbol (an)\left(\frac{a}{n}\right) (defined for odd n>1n>1 via multiplicativity over the prime factorization of nn) also satisfies reciprocity and the supplementary laws — but a Jacobi value of +1+1 does NOT guarantee that aa is a quadratic residue mod nn. For example (215)=(23)(25)=(−1)(−1)=+1\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=+1, yet 22 is a non-residue mod 1515 (it's a non-residue mod both 33 and 55). The Jacobi symbol speeds up computation but loses the QR interpretation for composite moduli.

Counterexample

Reciprocity does NOT say the two symbols are always equal. A common error is to drop the sign factor. Take p=3p=3, q=7q=7, both ≡3(mod4)\equiv 3\pmod 4. Then p−12⋅q−12=1⋅3=3\frac{p-1}{2}\cdot\frac{q-1}{2}=1\cdot 3=3 is odd, so [4] gives (37)(73)=−1\left(\frac{3}{7}\right)\left(\frac{7}{3}\right)=-1. Check: squares mod 7 are {1,2,4}\{1,2,4\}, so (37)=−1\left(\frac{3}{7}\right)=-1; and 7≡1(mod3)7\equiv1\pmod3 a square, so (73)=(13)=+1\left(\frac{7}{3}\right)=\left(\frac{1}{3}\right)=+1. Indeed (−1)(+1)=−1(-1)(+1)=-1. The symbols differ precisely because both primes are ≡3(mod4)\equiv 3\pmod 4 — exactly the case naive "they're always equal" reasoning gets wrong.

Connections

connection

Quadratic reciprocity sits at the crossroads of several theories. It is the simplest case of Artin Reciprocity in class field theory, where the Legendre symbol becomes an Artin symbol describing how primes split in abelian extensions. Through Gauss Sums and Cyclotomic Fields, the value (qp)\left(\frac{q}{p}\right) is encoded in the factorization of pp in Q(ζq)\mathbb{Q}(\zeta_q) and in Q(q∗)\mathbb{Q}(\sqrt{q^*}) where q∗=(−1)(q−1)/2qq^* = (-1)^{(q-1)/2}q. The multiplicative structure relies on Cyclic Groups (the group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times being cyclic) and on Fermat's Little Theorem. Generalizations to higher powers — Cubic Reciprocity and Biquadratic Reciprocity — require working in Z[ω]\mathbb{Z}[\omega] and Z[i]\mathbb{Z}[i], foreshadowing Algebraic Number Theory.

Real-World Applications

🔬 Where this appears

Historical Development

⏳ History
- 1640s–1650s — Fermat observes which primes are sums of two squares (p≡1(mod4)p\equiv1\pmod4), implicitly studying (−1p)\left(\frac{-1}{p}\right) and the residue of −1-1.
- 1744–1746 — Euler states empirical conjectures equivalent to quadratic reciprocity in correspondence and in Theoremata circa divisores numerorum, and proves Euler's criterion [2].
- 1785 — Legendre publishes a partial proof and introduces the Legendre symbol, formulating reciprocity in its modern symbolic form but with gaps (he assumed unproven results on primes in arithmetic progressions).
- April 8, 1796 — Gauss (age 19) completes the first rigorous proof, recording the date in his diary; he names it the theorema aureum.
- 1801 — Gauss publishes two complete proofs in Disquisitiones Arithmeticae, founding modern number theory and introducing congruence notation.
- 1808–1818 — Gauss discovers further proofs (sixth proof via Gauss sums), aiming at higher reciprocity laws.
- 1844–1850 — Eisenstein gives elegant lattice-point and Gauss-sum proofs (the one sketched above) and, with Jacobi, advances cubic/biquadratic reciprocity.
- 1880s — Hilbert, Kummer recast reciprocity via the Hilbert symbol and local-global product formulas, paving the way to class field theory.
- 1927 — Emil Artin proves Artin reciprocity, the sweeping generalization for abelian extensions that contains quadratic reciprocity as its most basic special case.

Subtleties & Limits

open-problem

Quadratic reciprocity is completely solved, but its generalizations drive active research. The Langlands program seeks a vast non-abelian reciprocity law linking Galois representations to automorphic forms; quadratic reciprocity is the abelian, rank-one tip of this iceberg. For higher power residues, Artin's reciprocity governs abelian extensions, but explicit, computable reciprocity laws for general algebraic number fields (the "explicit reciprocity laws" of Wiles, Coleman, and others in pp-adic settings) remain technically intricate. Open computational questions persist too: the quadratic residuosity problem — distinguishing genuine residues from pseudo-residues mod n=pqn=pq without the factorization — is believed hard, but no proof of its hardness exists; if quantum factoring (Shor's algorithm) renders factoring easy, the cryptographic schemes built on it collapse. Finally, fine statistical questions about the distribution of quadratic residues (least non-residue size, related to GRH) connect to deep conjectures about LL-functions.

See Also

Modular Arithmetic · Euler's Criterion · Jacobi Symbol · Gauss Sums · Primitive Roots · Cyclotomic Fields · Artin Reciprocity · Cubic Reciprocity · Biquadratic Reciprocity · Tonelli–Shanks Algorithm · Solovay–Strassen Primality Test