Engineering / Mathematics — Quadratic Residues
The Law of Quadratic Reciprocity
The law of quadratic reciprocity, its statement, and why it makes symbol evaluation efficient.
Executive summary
Quadratic reciprocity relates the solvability of x squared congruent to q modulo p with that of x squared congruent to p modulo q. The relationship is a simple sign rule depending on the residues of both primes modulo four.
Its computational value is that it permits the arguments of a Legendre symbol to be swapped, which turns evaluation into a Euclid-style reduction.
Learning objectives
- State the law and its sign condition.
- Explain its computational significance.
- Place it in mathematical context.
01The statement
Law of quadratic reciprocity
For distinct odd primes p and q:
(p|q)(q|p) = (−1)^{((p−1)/2)((q−1)/2)}.
Equivalently, (p|q) = (q|p) unless both p and q are congruent to 3 modulo 4, in which case (p|q) = −(q|p).
The surprise is that there should be any relationship at all. Whether q is a square modulo p concerns arithmetic in one system; whether p is a square modulo q concerns a different one. The law says the two questions have nearly the same answer, with a correction depending only on the residues modulo four.
| p mod 4 | q mod 4 | Relationship |
|---|---|---|
| 1 | 1 | (p|q) = (q|p) |
| 1 | 3 | (p|q) = (q|p) |
| 3 | 1 | (p|q) = (q|p) |
| 3 | 3 | (p|q) = −(q|p) |
02Why it makes evaluation fast
Reciprocity lets the two arguments be exchanged. Combined with reduction of the numerator modulo the denominator, this produces a strictly decreasing sequence exactly like the Euclidean algorithm.
Reduce the numerator
Replace a by a mod p, which does not change the symbol.
Extract factors of two
Apply the supplementary law for 2 repeatedly until the numerator is odd.
Flip by reciprocity
Swap numerator and denominator, adjusting the sign by the rule above.
Repeat
Arguments strictly decrease, so the process terminates in logarithmically many steps.
This is why symbol evaluation costs O(len(p)²) rather than the O(len(p)³) of Euler's criterion, and why it needs no factorisation of the numerator.
03Context
Reciprocity was conjectured by Euler and Legendre and first proved by Gauss, who called it the golden theorem and gave several distinct proofs over his lifetime. More than two hundred proofs are now known.
Why so many proofs
The law sits at the meeting point of several theories — Gauss sums, cyclotomy, counting lattice points, algebraic number theory — and each gives a different route.
Higher reciprocity
Cubic, quartic and general power reciprocity laws extend the pattern, and the search for them motivated much of algebraic number theory.
Artin reciprocity
The modern formulation places quadratic reciprocity as a special case of a general statement in class field theory.
For the purposes of this collection the law is a computational tool, but it is worth knowing that the tool is a shadow of a much larger structure, and that pursuing its generalisations built a substantial part of modern number theory.
04Frequently asked questions
Does reciprocity help decide residuosity modulo a composite?
It permits computing the Jacobi symbol without factoring, but a Jacobi symbol of plus one does not establish residuosity modulo a composite. That gap is the basis of the quadratic residuosity assumption.
Is there an elementary proof?
Several. Eisenstein's lattice-point counting proof is the most commonly presented and requires nothing beyond careful counting, though it is not short.
Why does the sign depend on residues modulo 4?
Because the quantity (p−1)/2 is even exactly when p ≡ 1 (mod 4), so the exponent in the sign formula is odd only when both primes are 3 mod 4. The condition is arithmetic bookkeeping in the exponent.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 285-287.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.