21.01.06 · number-theory / elementary

Quadratic residues, the Legendre symbol, and Euler's criterion

shipped3 tiersLean: none

Anchor (Master): Gauss 1801 *Disquisitiones Arithmeticae* arts. 95-152 (originator: quadratic residues, Legendre symbol, Euler's criterion, Gauss's lemma, the first complete proof of quadratic reciprocity, the theorema aureum); Euler 1744 *Comm. Acad. Petrop.* 14, 151-181 (special-case conjectures of reciprocity for divisors of $p a^2 + q b^2$); Legendre 1798 *Essai sur la théorie des nombres* (statement of the law and partial proof); Jacobi 1837 *J. reine angew. Math.* 30, 166-182 (Jacobi symbol $(a/n)$ for $n$ odd composite, reciprocity for the Jacobi symbol); Eisenstein 1844 *J. reine angew. Math.* 27, 289-310 (cubic and biquadratic reciprocity, lattice-point counting proof of quadratic reciprocity); Hilbert 1897 *Jahresber. DMV* 4, 175-546 (Hilbert reciprocity, general reciprocity in the *Zahlbericht*); Takagi 1920 *J. Coll. Sci. Tokyo* 41, 1-133 (class field theory for relatively abelian number fields); Artin 1927 *Hamb. Abh.* 5, 353-363 (Artin reciprocity, modern formulation of general reciprocity for abelian extensions); Tonelli 1891 *Göttinger Nachr.* 1891, 344-346 (square roots modulo $p$); Shanks 1972 *Proc. Second Manitoba Conf. Numer. Math.* 51-70 (Tonelli-Shanks algorithm); Goldwasser-Micali 1982 *STOC* 365-377 (probabilistic encryption from quadratic-residuosity); Hardy-Wright 2008 6e §§V-VII

Intuition Beginner

A quadratic residue modulo a prime $p$ is a nonzero residue that is the square of some other residue modulo $p$ . For the prime $p = 7$ , square each of the nonzero residues: $1^{2} = 1$ , $2^{2} = 4$ , $3^{2} = 9 \equiv 2 (mod 7)$ , $4^{2} = 16 \equiv 2 (mod 7)$ , $5^{2} = 25 \equiv 4 (mod 7)$ , $6^{2} = 36 \equiv 1 (mod 7)$ . The squares produce ${1, 2, 4}$ . So the quadratic residues modulo $7$ are ${1, 2, 4}$ , and the non-residues — the residues that are not squares — are ${3, 5, 6}$ .

The pattern repeats. For every odd prime $p$ , exactly half of the $p - 1$ nonzero residues are squares, and exactly half are not. Each nonzero square comes from exactly two square roots: $a^{2} \equiv (- a)^{2} (mod p)$ , and these two roots $\pm a$ are distinct because $p$ is odd. So the squaring map sends $p - 1$ inputs onto $(p - 1) /2$ outputs in a two-to-one fashion.

The Legendre symbol $(a / p)$ is a compact notation that records the quadratic-residue status of $a$ modulo $p$ . The value is $+ 1$ if $a$ is a nonzero quadratic residue modulo $p$ , $- 1$ if $a$ is a non-residue, and $0$ if $p$ divides $a$ . For example $(1/7) = (2/7) = (4/7) = + 1$ , $(3/7) = (5/7) = (6/7) = - 1$ , $(7/7) = 0$ .

Euler's criterion is the computational test: $(a / p) \equiv a^{(p - 1) /2} (mod p)$ for every $a$ . The right-hand side is a power computation that takes about $lo g_{2} p$ modular multiplications by repeated squaring, dramatically faster than searching for a square root. For $p = 7$ and $a = 5$ , compute $5^{3} = 125 = 17 \cdot 7 + 6 \equiv - 1 (mod 7)$ , confirming that $(5/7) = - 1$ and $5$ is a non-residue.

Why does this concept exist? Because the question "is $a$ a square modulo $p$ ?" is the most basic non-linear question in modular arithmetic, and its answer drives algorithms ranging from the Tonelli-Shanks square-root extraction (used to compress public keys in elliptic-curve cryptography) to the quadratic sieve (the second-fastest integer-factorisation algorithm known). The Legendre symbol packages the answer into a multiplicative structure that supports rapid computation.

Worked example: is $5$ a quadratic residue modulo $13$ ? By Euler's criterion, evaluate $5^{6} mod 13$ . Compute $5^{2} = 25 \equiv 12 \equiv - 1 (mod 13)$ , so $5^{6} = (5^{2})^{3} \equiv (- 1)^{3} = - 1 (mod 13)$ . So $(5/13) = - 1$ , and $5$ is not a square modulo $13$ . Cross-check by enumeration: the squares modulo $13$ are $1, 4, 9, 3, 12, 10$ — namely ${1, 3, 4, 9, 10, 12}$ — and $5$ is not on the list.

Visual Beginner

The picture shows the squaring map on the six nonzero residues modulo $7$ . Each arrow points from a residue to its square. The map collapses pairs ${a, - a}$ onto a single output, producing three quadratic residues from six inputs.

The picture captures the central numerical fact: each nonzero quadratic residue modulo an odd prime $p$ has exactly two square roots $\pm a$ , and the squaring map is two-to-one on $(Z / p Z)^{\times}$ . So among the $p - 1$ nonzero residues, exactly $(p - 1) /2$ are quadratic residues, and exactly $(p - 1) /2$ are non-residues.

Worked example Beginner

Determine whether $7$ is a quadratic residue modulo the prime $p = 17$ , using Euler's criterion.

Step 1. The exponent in Euler's criterion is $(p - 1) /2 = 8$ . We need to compute $7^{8} mod 17$ .

Step 2. Repeated squaring. Compute $7^{2} = 49 = 2 \cdot 17 + 15 \equiv 15 (mod 17)$ , so $7^{2} \equiv 15 \equiv - 2 (mod 17)$ .

Step 3. Square again: $7^{4} = (7^{2})^{2} \equiv (- 2)^{2} = 4 (mod 17)$ .

Step 4. Square once more: $7^{8} = (7^{4})^{2} \equiv 4^{2} = 16 \equiv - 1 (mod 17)$ .

Step 5. By Euler's criterion, $(7/17) \equiv 7^{8} \equiv - 1 (mod 17)$ , so $(7/17) = - 1$ .

Step 6. Conclusion: $7$ is a non-residue modulo $17$ , so the congruence $x^{2} \equiv 7 (mod 17)$ has no solutions in integers $x$ .

What this tells us: Euler's criterion converts the existence question "is $a$ a square modulo $p$ ?" into a single modular exponentiation, computable in $O (lo g p)$ steps by repeated squaring. No search through residue classes is needed. The value $7^{8} mod 17 = - 1$ is the result of three squarings — about $lo g_{2} (8) = 3$ steps — and the answer $- 1$ tells us $7$ has no square root modulo $17$ . Cross-check by listing the squares modulo $17$ : $1, 4, 9, 16, 8, 2, 15, 13$ — that is ${1, 2, 4, 8, 9, 13, 15, 16}$ . The residue $7$ is not on the list, confirming the criterion.

Check your understanding Beginner

Formal definition Intermediate+

We restate the quadratic-residue concepts in the precise language inherited from the cyclic structure of $(Z / p Z)^{\times}$ established in 21.01.05.

Definition (quadratic residue modulo $p$ ). Let $p$ be an odd prime and $a$ an integer with $g cd (a, p) = 1$ . The integer $a$ is a quadratic residue modulo $p$ if there exists $x \in Z$ with $x^{2} \equiv a (mod p)$ ; otherwise $a$ is a quadratic non-residue modulo $p$ . The set of quadratic residues modulo $p$ is denoted $QR_{p}$ ; the set of non-residues is denoted $NR_{p}$ .

Definition (Legendre symbol). Let $p$ be an odd prime. The Legendre symbol $(a / p)$ is defined for every integer $a$ by $$ \left(\frac{a}{p}\right) ;=; \begin{cases} +1, & a \in \mathrm{QR}_p \ -1, & a \in \mathrm{NR}_p \ 0, & p \mid a. \end{cases} $$ The Legendre symbol is a function $Z \to {- 1, 0, + 1}$ depending only on the residue class of $a$ modulo $p$ .

The Legendre symbol factors through $Z / p Z$ : $(a / p) = (b / p)$ whenever $a \equiv b (mod p)$ . Restricting to $(Z / p Z)^{\times}$ , the Legendre symbol is the unique non-identity group homomorphism $(Z / p Z)^{\times} \to {\pm 1}$ (the quadratic character modulo $p$ ), with kernel $QR_{p}$ .

Definition (squaring homomorphism). The map $σ_{p} : (Z / p Z)^{\times} \to (Z / p Z)^{\times}$ , $x \mapsto x^{2}$ , is a group homomorphism with kernel ${\pm 1}$ and image $QR_{p}$ . The exact sequence $$ 1 \to {\pm 1} \to (\mathbb{Z}/p\mathbb{Z})^\times \xrightarrow{\sigma_p} \mathrm{QR}_p \to 1 $$ identifies $QR_{p}$ as the image, of index $2$ in $(Z / p Z)^{\times}$ , with $∣ QR_{p} ∣ = (p - 1) /2$ .

Counterexamples to common slips

"The product of two quadratic non-residues is a non-residue." False: the product of two non-residues is a residue. The multiplicative property $(ab / p) = (a / p) (b / p)$ gives $(- 1) (- 1) = + 1$ . For instance $3, 5$ are both non-residues modulo $7$ , but $3 \cdot 5 = 15 \equiv 1 (mod 7)$ is the identity residue $1$ .
" $(a / p)$ is multiplicative as a function of $p$ too." False: the Legendre symbol $(a / p)$ is multiplicative in $a$ for fixed $p$ , but $(a / pq) \neq = (a / p) (a / q)$ in general. The latter would be the Jacobi symbol $(a / n)$ for $n$ odd composite — see Theorem 4 below — but it carries different information than the Legendre symbols for the individual prime factors.
"Euler's criterion $a^{(p - 1) /2} \equiv (a / p) (mod p)$ holds for $p = 2$ ." False: the formula requires $p$ odd. For $p = 2$ the exponent $(p - 1) /2 = 1/2$ is not an integer, and the Legendre symbol $(a /2)$ is not defined in the usual sense. Quadratic-residue theory modulo $2$ is degenerate: every odd integer is a square modulo $2$ (with $1 = 1^{2}$ ).

Key theorem with proof Intermediate+

The signature theorem of this unit is Euler's criterion, the bridge from the multiplicative structure of $(Z / p Z)^{\times}$ to the existence of square roots.

Theorem (Euler's criterion; Euler 1748, Gauss 1801 art. 106). Let $p$ be an odd prime and $a$ an integer with $g cd (a, p) = 1$ . Then $$ \left(\frac{a}{p}\right) ;\equiv; a^{(p - 1)/2} \pmod p. $$ Equivalently, $a^{(p - 1) /2} \equiv + 1 (mod p)$ if $a$ is a quadratic residue modulo $p$ , and $a^{(p - 1) /2} \equiv - 1 (mod p)$ if $a$ is a non-residue modulo $p$ .

Proof. Let $G = (Z / p Z)^{\times}$ , cyclic of order $p - 1$ by the Key Theorem of 21.01.05. Fix a primitive root $g$ modulo $p$ , so $G = {g^{0}, g^{1}, \dots, g^{p - 2}}$ . Every nonzero residue $a$ is $g^{k}$ for a unique $k \in {0, 1, \dots, p - 2}$ .

Step 1 — Squaring image. The image of the squaring map $σ_{p} : G \to G$ , $x \mapsto x^{2}$ , equals ${g^{2 j} : j \in Z / (p - 1)}$ . Since $p - 1$ is even, the powers $g^{2 j}$ are exactly the elements $g^{k}$ with $k$ even modulo $p - 1$ . So $a = g^{k}$ is a quadratic residue iff $k$ is even.

Step 2 — Compute $a^{(p - 1) /2}$ . For $a = g^{k}$ , $$ a^{(p - 1)/2} ;=; g^{k (p - 1)/2} ;=; \big(g^{(p - 1)/2}\big)^k. $$ The element $g^{(p - 1) /2}$ has order exactly $2$ in $G$ (since $g$ has order $p - 1$ and $(p - 1) /2$ is the maximal proper divisor), so $g^{(p - 1) /2} = - 1$ in $F_{p}$ (the unique element of order $2$ ). Hence $$ a^{(p - 1)/2} ;=; (-1)^k \pmod p. $$

Step 3 — Combine. $a$ is a quadratic residue iff $k$ is even (Step 1), iff $(- 1)^{k} = + 1$ (basic parity), iff $a^{(p - 1) /2} \equiv + 1 (mod p)$ (Step 2). By complementarity, $a$ is a non-residue iff $a^{(p - 1) /2} \equiv - 1 (mod p)$ . Combining with the Legendre-symbol definition gives $(a / p) \equiv a^{(p - 1) /2} (mod p)$ . $□$

Bridge. Euler's criterion builds toward 21.01.07 quadratic reciprocity, where the law $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ is the signature theorem; the criterion supplies the order- $2$ character interpretation that makes the law a statement about characters on $(Z / p)^{\times}$ and $(Z / q)^{\times}$ matching up. The central insight is exactly that the unique order- $2$ element $- 1 \in (Z / p)^{\times}$ — itself $g^{(p - 1) /2}$ for any primitive root $g$ — controls every quadratic phenomenon modulo $p$ : the Legendre symbol $(a / p)$ equals $+ 1$ or $- 1$ according to whether $a$ lies in the index- $2$ subgroup $QR_{p}$ or the other coset. The bridge is to the broader framework of 21.03.02 Dirichlet $L$ -functions, where the Legendre symbol $a \mapsto (a / p)$ extends to the quadratic Dirichlet character $χ_{p} : (Z / p)^{\times} \to C^{\times}$ and the $L$ -function $L (s, χ_{p}) = \sum_{n} χ_{p} (n) n^{- s}$ encodes the distribution of quadratic residues across arithmetic progressions. Putting these together, Euler's criterion is the elementary appearance of the principle that organises all of 21.03.03 $L$ -function reciprocity: characters of finite abelian groups detect coset memberships, and modular-power computations evaluate those characters in polynomial time.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove the multiplicative property of the Legendre symbol: for $p$ an odd prime and integers $a, b$ both coprime to $p$ , $$ \left(\frac{ab}{p}\right) ;=; \left(\frac{a}{p}\right) \left(\frac{b}{p}\right). $$

Hint

Use Euler's criterion: $(ab / p) \equiv (ab)^{(p - 1) /2} (mod p)$ , and expand using the laws of exponents.

Answer

By Euler's criterion, $$ \left(\frac{ab}{p}\right) ;\equiv; (ab)^{(p - 1)/2} ;=; a^{(p - 1)/2} \cdot b^{(p - 1)/2} ;\equiv; \left(\frac{a}{p}\right) \left(\frac{b}{p}\right) \pmod p. $$ Both sides are elements of ${- 1, + 1}$ (since both factors on the right are), and two elements of ${- 1, + 1}$ congruent modulo any odd prime $p \geq 3$ are equal. (The difference $\pm 1 - (\pm 1) \in {- 2, 0, 2}$ is divisible by $p \geq 3$ only when the difference is $0$ .) Hence the equality holds as integers.

Consequences: the product of two quadratic residues is a residue ( $(+ 1) (+ 1) = + 1$ ); the product of two non-residues is a residue ( $(- 1) (- 1) = + 1$ ); the product of a residue and a non-residue is a non-residue ( $(+ 1) (- 1) = - 1$ ). The Legendre symbol restricted to $(Z / p)^{\times}$ is a group homomorphism into ${\pm 1}$ .

Rubric: full credit for the Euler-criterion expansion and the ${- 1, + 1}$ -valued lift from the modular congruence to integer equality.

Exercise 5 (medium, symbolic).

Prove the first supplementary law: for $p$ an odd prime, $$ \left(\frac{-1}{p}\right) ;=; \begin{cases} +1, & p \equiv 1 \pmod 4 \ -1, & p \equiv 3 \pmod 4. \end{cases} $$

Hint

Use Euler's criterion: $(- 1/ p) \equiv (- 1)^{(p - 1) /2} (mod p)$ . Then analyse the parity of $(p - 1) /2$ .

Answer

By Euler's criterion, $(- 1/ p) \equiv (- 1)^{(p - 1) /2} (mod p)$ , and since both sides are in ${- 1, + 1}$ and $p \geq 3$ , the congruence lifts to integer equality $(- 1/ p) = (- 1)^{(p - 1) /2}$ .

Case $p \equiv 1 (mod 4)$ : write $p = 4 k + 1$ , so $(p - 1) /2 = 2 k$ is even, and $(- 1)^{2 k} = + 1$ . Hence $(- 1/ p) = + 1$ and $- 1$ is a quadratic residue modulo $p$ .

Case $p \equiv 3 (mod 4)$ : write $p = 4 k + 3$ , so $(p - 1) /2 = 2 k + 1$ is odd, and $(- 1)^{2 k + 1} = - 1$ . Hence $(- 1/ p) = - 1$ and $- 1$ is a non-residue modulo $p$ .

Numerical illustrations: $p = 5 \equiv 1 (mod 4)$ , $(- 1/5) = + 1$ , and indeed $2^{2} = 4 \equiv - 1 (mod 5)$ . $p = 7 \equiv 3 (mod 4)$ , $(- 1/7) = - 1$ , and indeed $- 1 \equiv 6 \in / {1, 2, 4}$ — the residues modulo $7$ . $p = 13 \equiv 1 (mod 4)$ , $(- 1/13) = + 1$ , and $5^{2} = 25 \equiv - 1 (mod 13)$ .

Application: $p \equiv 1 (mod 4)$ characterises the primes for which $- 1$ is a quadratic residue, which is the same as the primes that can be written as a sum of two squares $p = a^{2} + b^{2}$ — a theorem of Fermat (1640) proved by Euler (1755) 21.01.04.

Rubric: full credit for the Euler-criterion application and both case analyses.

Exercise 6 (medium, symbolic).

Prove Gauss's lemma: for $p$ an odd prime and $a$ an integer coprime to $p$ , $$ \left(\frac{a}{p}\right) ;=; (-1)^\mu, $$ where $μ$ is the number of elements of the set ${a, 2 a, 3 a, \dots, ((p - 1) /2) a}$ whose least positive residue modulo $p$ exceeds $p /2$ .

Hint

Reduce each element $j a$ for $j = 1, \dots, (p - 1) /2$ to its least absolute residue modulo $p$ : write $j a \equiv ϵ_{j} r_{j} (mod p)$ with $ϵ_{j} \in {\pm 1}$ and $r_{j} \in {1, 2, \dots, (p - 1) /2}$ . Show the $r_{j}$ are a permutation of ${1, 2, \dots, (p - 1) /2}$ , then multiply.

Answer

For each $j \in {1, 2, \dots, (p - 1) /2}$ , the least positive residue of $j a$ modulo $p$ is in ${1, 2, \dots, p - 1}$ . Write $$ j a ;\equiv; \epsilon_j r_j \pmod p \quad \text{with } r_j \in {1, 2, \ldots, (p - 1)/2}, ;; \epsilon_j \in {\pm 1}, $$ where $ϵ_{j} = + 1$ if $j a mod p \in {1, \dots, (p - 1) /2}$ and $ϵ_{j} = - 1$ if $j a mod p \in {(p + 1) /2, \dots, p - 1}$ . So $μ = # {j : ϵ_{j} = - 1}$ .

Claim: the values $r_{1}, r_{2}, \dots, r_{(p - 1) /2}$ are a permutation of ${1, 2, \dots, (p - 1) /2}$ . Distinctness: if $r_{i} = r_{j}$ then $ia \equiv \pm j a (mod p)$ . Since $g cd (a, p) = 1$ , cancelling gives $i \equiv \pm j (mod p)$ . With $i, j \in {1, \dots, (p - 1) /2}$ , the $+$ case gives $i = j$ , and the $-$ case gives $i + j \equiv 0 (mod p)$ which forces $i + j \geq p$ , impossible since $i + j \leq p - 1$ . So all $r_{j}$ are distinct in ${1, \dots, (p - 1) /2}$ , hence form a permutation.

Multiply: $\prod_{j} (j a) \equiv \prod_{j} (ϵ_{j} r_{j}) = (\prod_{j} ϵ_{j}) \cdot \prod_{j} r_{j} (mod p)$ . The left side is $a^{(p - 1) /2} \cdot ((p - 1) /2)!$ . The right side is $(- 1)^{μ} \cdot ((p - 1) /2)!$ (since the $r_{j}$ permute ${1, \dots, (p - 1) /2}$ ). Cancelling $((p - 1) /2)!$ (which is coprime to $p$ ): $$ a^{(p - 1)/2} ;\equiv; (-1)^\mu \pmod p. $$ By Euler's criterion, the left side equals $(a / p)$ as an integer in ${\pm 1}$ . So $(a / p) = (- 1)^{μ}$ .

Application: Gauss's lemma yields the second supplementary law $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ by setting $a = 2$ and counting: the set ${2, 4, \dots, p - 1}$ has $μ = ⌊(p + 1) /4 ⌋$ or equivalently $μ$ even iff $p \equiv \pm 1 (mod 8)$ .

Rubric: full credit for the permutation argument and the product-and-cancel step.

Exercise 7 (hard, symbolic).

Use Gauss's lemma to prove the second supplementary law: for $p$ an odd prime, $$ \left(\frac{2}{p}\right) ;=; \begin{cases} +1, & p \equiv \pm 1 \pmod 8 \ -1, & p \equiv \pm 3 \pmod 8. \end{cases} $$ Equivalently, $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ .

Hint

Apply Gauss's lemma with $a = 2$ . The set ${2, 4, 6, \dots, p - 1}$ has $(p - 1) /2$ elements; count how many exceed $p /2$ .

Answer

By Gauss's lemma, $(2/ p) = (- 1)^{μ}$ where $μ = # {j : 1 \leq j \leq (p - 1) /2, (2 j) mod p > p /2}$ . The values of $2 j$ for $j$ in that range are $2, 4, 6, \dots, p - 1$ — all already in ${1, \dots, p - 1}$ so $(2 j) mod p = 2 j$ — and we count those exceeding $p /2$ .

So $μ = # {j : 1 \leq j \leq (p - 1) /2, 2 j > p /2} = # {j : p /4 < j \leq (p - 1) /2}$ .

The count: $μ = (p - 1) /2 - ⌊ p /4 ⌋$ .

Case $p = 8 k + 1$ : $⌊ p /4 ⌋ = 2 k$ , $(p - 1) /2 = 4 k$ , so $μ = 4 k - 2 k = 2 k$ , even. Hence $(2/ p) = + 1$ .

Case $p = 8 k + 3$ : $⌊ p /4 ⌋ = 2 k$ , $(p - 1) /2 = 4 k + 1$ , so $μ = 2 k + 1$ , odd. Hence $(2/ p) = - 1$ .

Case $p = 8 k + 5$ : $⌊ p /4 ⌋ = 2 k + 1$ , $(p - 1) /2 = 4 k + 2$ , so $μ = 2 k + 1$ , odd. Hence $(2/ p) = - 1$ .

Case $p = 8 k + 7$ : $⌊ p /4 ⌋ = 2 k + 1$ , $(p - 1) /2 = 4 k + 3$ , so $μ = 2 k + 2$ , even. Hence $(2/ p) = + 1$ .

Collecting cases: $(2/ p) = + 1$ iff $p \equiv 1, 7 (mod 8)$ , i.e., $p \equiv \pm 1 (mod 8)$ ; $(2/ p) = - 1$ iff $p \equiv 3, 5 (mod 8)$ , i.e., $p \equiv \pm 3 (mod 8)$ .

The unified form $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ : for $p$ odd, $p^{2} \equiv 1 (mod 8)$ (since $p \in {1, 3, 5, 7} (mod 8)$ gives $p^{2} \in {1, 9, 25, 49} (mod 8)$ , all $\equiv 1$ ); so $(p^{2} - 1) /8 \in Z$ . Direct check: $p \equiv 1 (mod 8) \Rightarrow (p^{2} - 1) /8$ is even; $p \equiv 3 (mod 8) \Rightarrow (p^{2} - 1) /8 = (9 + 24 k + 64 k^{2} - 1) /8 = 1 + 3 k + 8 k^{2}$ which is odd iff $1 + 3 k$ is odd iff $k$ is even — checking $p = 3, 11, 19, \dots$ : indeed $(2/3) = - 1$ , $(2/11) = - 1$ , $(2/19) = - 1$ . The four cases collapse to the announced formula.

Numerical: $(2/7) = + 1$ ( $7 \equiv - 1 (mod 8)$ ; indeed $3^{2} = 9 \equiv 2 (mod 7)$ ). $(2/11) = - 1$ ( $11 \equiv 3 (mod 8)$ ; the squares modulo $11$ are ${1, 3, 4, 5, 9}$ , and $2$ is not on the list). $(2/17) = + 1$ ( $17 \equiv 1 (mod 8)$ ; $6^{2} = 36 \equiv 2 (mod 17)$ , from Exercise 2 above).

Rubric: full credit for the four-case Gauss-lemma counting argument and the unified $(p^{2} - 1) /8$ formula.

Exercise 8 (hard, symbolic).

State the law of quadratic reciprocity and verify it for the pair $(p, q) = (7, 11)$ by independent computation of $(7/11)$ and $(11/7)$ .

Hint

The law: for $p, q$ distinct odd primes, $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . Compute $(7/11)$ and $(11/7)$ separately by Euler's criterion or by reduction, then check the product equals the predicted sign.

Answer

Statement (Gauss 1801). For distinct odd primes $p, q$ , $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ Equivalently, $(p / q) = (q / p)$ unless both $p \equiv q \equiv 3 (mod 4)$ , in which case $(p / q) = - (q / p)$ .

Verification for $(p, q) = (7, 11)$ . Both primes are $\equiv 3 (mod 4)$ , so the law predicts $(7/11) = - (11/7)$ .

Compute $(7/11)$ by Euler's criterion: $(7/11) \equiv 7^{5} (mod 11)$ . $7^{2} = 49 \equiv 5 (mod 11)$ ; $7^{4} \equiv 25 \equiv 3 (mod 11)$ ; $7^{5} \equiv 7 \cdot 3 = 21 \equiv - 1 (mod 11)$ . So $(7/11) = - 1$ . (Cross-check: squares modulo $11$ are ${1, 3, 4, 5, 9}$ , and $7$ is not on the list.)

Compute $(11/7) = (4/7)$ since $11 \equiv 4 (mod 7)$ . And $4 = 2^{2}$ is the square of $2$ modulo $7$ , so $(4/7) = + 1$ . (Direct check: $2^{2} = 4$ .)

Verify the law: $(7/11) \cdot (11/7) = (- 1) (+ 1) = - 1$ , and the predicted exponent is $((7 - 1) /2) ((11 - 1) /2) = 3 \cdot 5 = 15$ , odd, giving $(- 1)^{15} = - 1$ . The product equals the predicted sign.

(Full proof of quadratic reciprocity is deferred to 21.01.07, the dedicated unit on reciprocity. The standard proofs include Gauss's first proof by induction (Gauss 1801 arts. 135-145), Gauss's third proof by counting fixed points of a permutation (Gauss 1808), Eisenstein's lattice-point-counting proof (Eisenstein 1844), and the Gauss-sum-based proof via cyclotomic fields (Dirichlet 1854).)

Rubric: full credit for the correct statement, the two independent Legendre-symbol computations, and the verification of the predicted sign.

Lean formalization Intermediate+

Mathlib supplies the abstract scaffolding for the Legendre symbol and Euler's criterion. The relevant declarations live in Mathlib.NumberTheory.LegendreSymbol.

-- Operative imports: Mathlib.NumberTheory.LegendreSymbol.Basic,
-- Mathlib.NumberTheory.LegendreSymbol.QuadraticReciprocity,
-- Mathlib.NumberTheory.LegendreSymbol.GaussSum

#check @ZMod.legendreSym
-- The Legendre symbol (a/p) : ZMod p → ℤ, valued in {-1, 0, 1}.

#check @ZMod.euler_criterion
-- (a/p) ≡ a^((p - 1) / 2) (mod p) for p odd prime and a coprime to p.

#check @ZMod.legendreSym_one
-- (1/p) = 1.

#check @ZMod.legendreSym_neg_one
-- (-1/p) = (-1)^((p - 1) / 2), the first supplementary law.

#check @ZMod.legendreSym_two
-- (2/p) = (-1)^((p^2 - 1) / 8), the second supplementary law.

#check @ZMod.quadraticReciprocity
-- (p/q) * (q/p) = (-1)^((p - 1)/2 * (q - 1)/2), the main reciprocity law.

#check @ZMod.exists_sq_eq_iff_legendreSym_eq_one
-- a is a quadratic residue modulo p iff (a/p) = 1 (for a coprime to p).

The Mathlib formalisation is comprehensive at the level of the law itself, the two supplementary laws, and the Euler-criterion identity. What Mathlib has not yet packaged: the explicit Tonelli-Shanks algorithm for computing $a (mod p)$ when $(a / p) = + 1$ , with a constructive correctness proof in $O ((lo g p)^{2} + (lo g p) S^{2})$ time where $2^{S} ∥ p - 1$ ; the binary Jacobi-symbol algorithm via repeated reciprocity steps (the standard $O ((lo g n)^{2})$ algorithm in cryptographic libraries); the Goldwasser-Micali probabilistic-encryption security reduction from the quadratic-residuosity assumption modulo $n = pq$ ; the explicit link from the Legendre symbol to the Hilbert symbol $(a, b)_{p}$ at the prime $p$ and the product formula $\prod_{v} (a, b)_{v} = 1$ . These are the formalisation gaps documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (Euler's criterion). For $p$ an odd prime and $a$ coprime to $p$ , $(a / p) \equiv a^{(p - 1) /2} (mod p)$ ^{[Gauss 1801]}. Proved above as the Key Theorem via the cyclic structure of $(Z / p)^{\times}$ and the order- $2$ element $- 1$ . Euler himself stated this in 1748 Comm. Acad. Petrop. without the explicit Legendre symbol (which appeared in Legendre 1798); Gauss 1801 article 106 gave the modern formulation.

Theorem 2 (Gauss's lemma). For $p$ an odd prime and $a$ coprime to $p$ , $(a / p) = (- 1)^{μ}$ where $μ$ is the number of $j \in {1, 2, \dots, (p - 1) /2}$ for which the least positive residue of $j a$ modulo $p$ exceeds $p /2$ ^{[Gauss 1801]}. Proved above as Exercise 6 via the permutation-of-absolute-residues argument. Gauss's lemma is the operational tool for proving the two supplementary laws (Exercises 5, 7) and is one of the eight independent proof routes Gauss took for the full reciprocity law.

Theorem 3 (Quadratic reciprocity; Gauss 1801, theorema aureum). For distinct odd primes $p, q$ , $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ Equivalently, $(p / q) = (q / p)$ unless $p \equiv q \equiv 3 (mod 4)$ , in which case $(p / q) = - (q / p)$ ^{[Gauss 1801]}. Gauss called the law the theorema aureum — "the golden theorem" — and announced his first complete proof in his mathematical diary entry of April 1796, formalised in Disquisitiones Arithmeticae articles 125-152. Gauss produced eight independent proofs over his lifetime: the original induction proof (1796/1801), the Gauss-sum proof (Gauss 1811 Werke II), the lemma-and-counting proof (Gauss 1818), the cyclotomic proof (Gauss 1818), and four more proofs in Werke II. Today more than $300$ independent proofs are known (Lemmermeyer 2000 Reciprocity Laws catalogues most of them). The full proof is deferred to 21.01.07.

Theorem 4 (Jacobi symbol and its reciprocity; Jacobi 1837). For $n$ odd positive composite with prime factorisation $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ and $a$ coprime to $n$ , the Jacobi symbol is $$ \left(\frac{a}{n}\right) ;=; \prod_{i = 1}^k \left(\frac{a}{p_i}\right)^{e_i}. $$ The Jacobi symbol satisfies $(a / n) (b / n) = (ab / n)$ (multiplicativity) and the reciprocity law $(m / n) (n / m) = (- 1)^{((m - 1) /2) ((n - 1) /2)}$ for $m, n$ odd coprime positive, plus the supplementary laws $(- 1/ n) = (- 1)^{(n - 1) /2}$ and $(2/ n) = (- 1)^{(n^{2} - 1) /8}$ ^{[Jacobi 1837]}. The Jacobi symbol crucially does not detect quadratic residuosity in general — $(a / n) = + 1$ does not imply $a$ is a square modulo $n$ when $n$ is composite — but it does enable the binary Jacobi-symbol algorithm: compute $(a / n)$ in $O ((lo g n)^{2})$ time by alternating reduction $a mod n$ and reciprocity flip $(a / n) \leftrightarrow \pm (n / a)$ without factoring $n$ . This is the algorithm used in OpenSSL, GMP, and every standard cryptographic library for primality-testing pre-checks and computing Legendre symbols quickly.

Theorem 5 (Tonelli-Shanks square-root algorithm; Tonelli 1891, Shanks 1972). Let $p$ be an odd prime, $a$ a quadratic residue modulo $p$ . The square root $a (mod p)$ can be computed in expected time $O ((lo g p)^{2} + (lo g p) S^{2})$ where $2^{S} ∥ p - 1$ ^{[Shanks 1972]}. Write $p - 1 = 2^{S} Q$ with $Q$ odd. Find a non-residue $z$ modulo $p$ (random search succeeds in $2$ tries on average since half the residues are non-residues); set $c = z^{Q}$ , which has order exactly $2^{S}$ in $(Z / p)^{\times}$ . Initialise $r = a^{(Q + 1) /2}$ , $t = a^{Q}$ , $m = S$ ; while $t \neq = 1$ find the smallest $i$ with $t^{2^{i}} = 1$ , then update $b = c^{2^{m - i - 1}}$ , $r \mapsto r b$ , $t \mapsto t b^{2}$ , $c \mapsto b^{2}$ , $m \mapsto i$ . Terminates when $t = 1$ with $r$ a square root of $a$ . The Tonelli 1891 Göttinger Nachr. algorithm preceded Shanks's refinement; the combined Tonelli-Shanks method is the standard square-root algorithm in cryptography (elliptic-curve point decompression in EdDSA, ECDSA, BLS12-381 pairing-friendly curves).

Theorem 6 (Goldwasser-Micali probabilistic encryption; Goldwasser-Micali 1982). Let $n = pq$ be an RSA modulus (product of two large primes) and $y$ a pseudosquare modulo $n$ — i.e., $(y / n) = + 1$ via the Jacobi symbol but $y$ is not a quadratic residue modulo $n$ . The encryption scheme: to encrypt a bit $b \in {0, 1}$ , pick random $r \in (Z / n)^{\times}$ and output ciphertext $c = y^{b} r^{2} mod n$ . Decryption: $c$ decrypts to $0$ iff $c$ is a quadratic residue modulo $n$ , testable via the Legendre symbol $(c / p)$ using the secret factorisation. Semantic security follows from the quadratic-residuosity assumption: distinguishing pseudosquares from squares modulo $n$ is computationally hard given only $n$ ^{[Goldwasser-Micali 1982]}. This is the first semantically secure public-key encryption scheme — the founding example of the modern provable-security paradigm. The ciphertext is one bit per group element ( $lo g_{2} n \approx 2048$ bits per bit of plaintext), making the scheme inefficient in practice but a clean theoretical model. Refinements include Paillier 1999 EUROCRYPT (additively homomorphic, more efficient per bit) and the bilinear-pairing reformulation in identity-based encryption (Boneh-Franklin 2001).

Theorem 7 (Hilbert reciprocity; Hilbert 1897). For $a, b \in Q^{\times}$ , the Hilbert symbol $(a, b)_{v} \in {\pm 1}$ at each place $v$ of $Q$ (finite primes and the archimedean place) detects whether the quadratic form $Z^{2} - a X^{2} - b Y^{2}$ has a non-zero solution in $Q_{v}$ . The product formula $$ \prod_v (a, b)_v ;=; 1 $$ holds, with all but finitely many factors equal to $+ 1$ ^{[Hilbert 1897]}. The Hilbert symbol at a finite prime $p$ relates to the Legendre symbol: for $u, v \in Z_{p}^{\times}$ units, $(u, p)_{p} = (\overset{u}{ˉ} / p)$ where $\overset{u}{ˉ}$ is the reduction modulo $p$ . The product formula encodes quadratic reciprocity in the cleanest form: matching the signs at the two finite primes $p, q$ and the archimedean place gives $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . Hilbert's Zahlbericht (1897) developed this in the Theorie der algebraischen Zahlkörper §§64-90, and Hilbert's 9th problem (1900 ICM Paris) asked for the most general reciprocity law in any algebraic number field. The general reciprocity programme is the framework that organises every subsequent reciprocity law.

Theorem 8 (Artin reciprocity; Takagi 1920, Artin 1927). For $L / K$ a finite abelian extension of number fields, the Artin map induces an isomorphism $$ \mathrm{Art}{L/K} : I_K(\mathfrak{m}) / N{L/K}(I_L(\mathfrak{m})) P_{L/K}(\mathfrak{m}) ;\xrightarrow{\sim}; \mathrm{Gal}(L/K), $$ where $I_{K} (m)$ is the group of fractional ideals of $K$ coprime to a conductor $m$ , $N$ is the norm map, $P$ is the principal ideal subgroup, and the map sends a prime $p$ to its Frobenius element $Frob_{p} \in Gal (L / K)$ ^{[Artin 1927]}. Specialised to the quadratic extension $L = Q (p^{*}) / Q$ where $p^{*} = (- 1)^{(p - 1) /2} p$ is the signed prime, the Artin map sends $q$ to the Frobenius $Frob_{q}$ , whose image in $Gal (L / Q) = {\pm 1}$ is $(p^{*} / q)$ . The Artin map's compatibility with the conductor recovers quadratic reciprocity. Takagi 1920 J. Coll. Sci. Tokyo 41 had proved existence of the abelian-extension classification; Artin 1927 Hamb. Abh. 5 added the explicit Frobenius-isomorphism formulation, the "Artin reciprocity law." The non-abelian generalisation is the Langlands programme: Artin reciprocity = abelian Langlands; Langlands functoriality conjectures (Langlands 1967 letter to Weil; Langlands 1970 Yale Lectures) extend to all reductive groups via $L$ -functions of automorphic representations.

Synthesis. The quadratic-residue framework is the foundational reason that the cyclic structure of $(Z / p)^{\times}$ admits a clean index- $2$ subgroup of squares, with the Legendre symbol $(a / p)$ identifying the coset and Euler's criterion computing it via the single modular power $a^{(p - 1) /2}$ . The central insight is exactly that the unique order- $2$ element $- 1 \in (Z / p)^{\times}$ — itself $g^{(p - 1) /2}$ for any primitive root $g$ — controls every quadratic phenomenon: the squares are the kernel of the unique order- $2$ character $χ_{p} : (Z / p)^{\times} \to {\pm 1}$ , and the Legendre symbol is the explicit evaluation of $χ_{p}$ . Putting these together with multiplicativity, the two supplementary laws ( $(- 1/ p)$ , $(2/ p)$ ), Gauss's lemma, and the law of quadratic reciprocity, the entire quadratic-character theory of $Q$ is captured by the Legendre symbol with $O ((lo g p)^{2})$ -time computation via the Jacobi-symbol binary algorithm. The bridge is to the broader framework of 21.03.02 Dirichlet $L$ -functions and 21.03.03 Hecke and Artin $L$ -functions, where the Legendre symbol extends to general characters of generalised ideal class groups, and to the Langlands programme as the non-abelian extension.

The historical arc from Euler 1744 to Artin 1927 is the canonical example of how an elementary observation grows into a structural principle. Euler 1744 Comm. Acad. Petrop. 14 conjectured special cases of quadratic reciprocity disguised as theorems about divisors of $p a^{2} + q b^{2}$ ; Legendre 1798 Essai sur la théorie des nombres gave the statement in the modern symbol form (with an incomplete proof depending on the unproven Dirichlet theorem on primes in arithmetic progressions); Gauss 1801 articles 125-152 gave the first complete proof. Jacobi 1837 J. reine angew. Math. 30 extended to the Jacobi symbol with the algorithmic consequence of efficient computation; Eisenstein 1844 J. reine angew. Math. 27 added cubic and biquadratic reciprocity in the cyclotomic rings $Z [ζ_{3}]$ and $Z [i]$ ; Hilbert 1897 Jahresber. DMV 4 generalised to the Hilbert symbol and the product formula, with the 9th Hilbert problem (1900) asking for the most general reciprocity. Takagi 1920 and Artin 1927 completed the classical reciprocity programme via class field theory for abelian extensions of number fields. The non-abelian generalisation is the Langlands programme (Langlands 1967, 1970), and Wiles-Taylor 1995 Ann. Math. 142 proved the modularity theorem for elliptic curves over $Q$ as the first non-abelian Langlands reciprocity case.

The applied half builds the modern cryptographic infrastructure. Tonelli 1891 Göttinger Nachr. and Shanks 1972 Proc. Manitoba gave the deterministic square-root algorithm used in elliptic-curve point decompression (every ECDSA signature, every Edwards-curve EdDSA verification, every BLS aggregate signature). Goldwasser-Micali 1982 STOC founded the modern provable-security paradigm with the first semantically-secure encryption scheme from the quadratic-residuosity assumption. The pattern recurs in the quadratic sieve of Pomerance 1985 Lecture Notes Math. 1122, the second-fastest integer-factorisation algorithm — find smooth values of $f (x) = x^{2} - n$ over a factor base, build a linear system in $F_{2}$ , and solve to produce a non-degenerate congruence of squares $x^{2} \equiv y^{2} (mod n)$ from which $g cd (x - y, n)$ is a factor of $n$ . The same quadratic-residue framework that Gauss laid out in Disquisitiones Arithmeticae arts. 95-152 underlies every modern public-key cryptographic protocol where modular square roots appear, from RSA (Rabin variant) to elliptic-curve point compression to bilinear-pairing-based signatures.

Full proof set Master

Proposition 1 (Euler's criterion). For $p$ an odd prime and $a$ coprime to $p$ , $(a / p) \equiv a^{(p - 1) /2} (mod p)$ .

Proof. Reprised from the Key Theorem with sharpened notation. Let $G = (Z / p Z)^{\times}$ , cyclic of order $p - 1$ (Theorem 21.01.05.1). Fix a primitive root $g$ , so every $a \in G$ is $g^{k}$ for a unique $k \in Z / (p - 1)$ .

The squaring image is ${g^{2 j} : j \in Z / (p - 1)} = {g^{k} : k even modulo p - 1}$ . Since $p - 1$ is even, this is exactly the index- $2$ subgroup of even powers, of order $(p - 1) /2$ . So $a = g^{k}$ is a quadratic residue iff $k$ is even.

The element $g^{(p - 1) /2}$ has order $2$ in $G$ : $(g^{(p - 1) /2})^{2} = g^{p - 1} = 1$ , and the only smaller power is $g^{0} = 1$ , distinct from $g^{(p - 1) /2}$ since the order of $g$ is $p - 1$ . In a field, the only solutions of $x^{2} = 1$ are $x = \pm 1$ , so $g^{(p - 1) /2} \in {+ 1, - 1}$ , and it is not $+ 1$ (else the order of $g$ would divide $(p - 1) /2 < p - 1$ ). Hence $g^{(p - 1) /2} = - 1$ in $F_{p}$ .

Compute: $a^{(p - 1) /2} = g^{k (p - 1) /2} = (g^{(p - 1) /2})^{k} = (- 1)^{k} (mod p)$ . By the squaring-image analysis, $a$ is a quadratic residue iff $k$ is even iff $(- 1)^{k} = + 1$ iff $a^{(p - 1) /2} \equiv + 1 (mod p)$ . The complementary case gives the non-residue branch. So $(a / p) \equiv a^{(p - 1) /2} (mod p)$ . $□$

Proposition 2 (multiplicativity). For $p$ an odd prime and $a, b$ coprime to $p$ , $(ab / p) = (a / p) (b / p)$ .

Proof. By Euler's criterion, $$ \left(\frac{ab}{p}\right) ;\equiv; (ab)^{(p - 1)/2} ;=; a^{(p - 1)/2} \cdot b^{(p - 1)/2} ;\equiv; \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) \pmod p. $$ Both sides are in ${- 1, + 1}$ . For $p \geq 3$ , two elements of ${- 1, + 1}$ congruent modulo $p$ are equal as integers (since the difference lies in ${- 2, 0, 2}$ , and $p \geq 3$ divides this only when the difference is $0$ ). $□$

Proposition 3 (first supplementary law). For $p$ an odd prime, $(- 1/ p) = + 1$ if $p \equiv 1 (mod 4)$ and $(- 1/ p) = - 1$ if $p \equiv 3 (mod 4)$ .

Proof. By Euler's criterion, $(- 1/ p) = (- 1)^{(p - 1) /2}$ as integers in ${- 1, + 1}$ . Case $p = 4 k + 1$ : $(p - 1) /2 = 2 k$ even, $(- 1)^{2 k} = + 1$ . Case $p = 4 k + 3$ : $(p - 1) /2 = 2 k + 1$ odd, $(- 1)^{2 k + 1} = - 1$ . $□$

Proposition 4 (Gauss's lemma). For $p$ an odd prime and $a$ coprime to $p$ , $(a / p) = (- 1)^{μ}$ where $μ$ is the number of $j \in {1, 2, \dots, (p - 1) /2}$ for which $(j a) mod p > p /2$ .

Proof. For each $j \in {1, \dots, (p - 1) /2}$ , write $$ j a ;\equiv; \epsilon_j r_j \pmod p, \quad r_j \in {1, 2, \ldots, (p - 1)/2}, ;; \epsilon_j \in {\pm 1}, $$ choosing $ϵ_{j} = - 1$ exactly when $(j a) mod p > p /2$ .

The values $r_{1}, \dots, r_{(p - 1) /2}$ are pairwise distinct in ${1, \dots, (p - 1) /2}$ , hence a permutation. If $r_{i} = r_{j}$ with $i \neq = j$ , then $ia \equiv \pm j a (mod p)$ , cancelling $a$ gives $i \equiv \pm j (mod p)$ . With $i, j \in {1, \dots, (p - 1) /2}$ , the $+$ case forces $i = j$ (contradiction), and the $-$ case forces $i + j \equiv 0 (mod p)$ which requires $i + j \geq p$ — impossible since $i + j \leq p - 1$ .

Multiply the relations: $\prod_{j = 1}^{(p - 1) /2} j a = (\prod_{j} ϵ_{j}) \prod_{j} r_{j}$ , so $$ a^{(p - 1)/2} \cdot ((p - 1)/2)! ;\equiv; (-1)^\mu \cdot ((p - 1)/2)! \pmod p. $$ Cancelling $((p - 1) /2)!$ (coprime to $p$ ): $a^{(p - 1) /2} \equiv (- 1)^{μ} (mod p)$ . By Euler's criterion (Proposition 1), the left side is $(a / p)$ in ${- 1, + 1}$ . So $(a / p) = (- 1)^{μ}$ . $□$

Proposition 5 (second supplementary law). For $p$ an odd prime, $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ .

Proof. Apply Gauss's lemma (Proposition 4) with $a = 2$ . The set ${2, 4, \dots, p - 1}$ has $(p - 1) /2$ elements, and $μ = # {j : p /4 < j \leq (p - 1) /2} = (p - 1) /2 - ⌊ p /4 ⌋$ .

Four cases by $p mod 8$ :

$p = 8 k + 1$ : $μ = 4 k - 2 k = 2 k$ even, so $(2/ p) = + 1$ .
$p = 8 k + 3$ : $μ = (4 k + 1) - 2 k = 2 k + 1$ odd, so $(2/ p) = - 1$ .
$p = 8 k + 5$ : $μ = (4 k + 2) - (2 k + 1) = 2 k + 1$ odd, so $(2/ p) = - 1$ .
$p = 8 k + 7$ : $μ = (4 k + 3) - (2 k + 1) = 2 k + 2$ even, so $(2/ p) = + 1$ .

So $(2/ p) = + 1$ iff $p \equiv \pm 1 (mod 8)$ , $- 1$ iff $p \equiv \pm 3 (mod 8)$ . Direct check: $(p^{2} - 1) /8 mod 2 = 0$ iff $p \equiv \pm 1 (mod 8)$ . So $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ . $□$

Proposition 6 (correctness of the Tonelli-Shanks algorithm). Given $p$ an odd prime, $a$ a quadratic residue modulo $p$ , the Tonelli-Shanks algorithm outputs $r$ with $r^{2} \equiv a (mod p)$ .

Proof. Write $p - 1 = 2^{S} Q$ with $Q$ odd. Let $z$ be a quadratic non-residue modulo $p$ (so $z^{Q}$ has order exactly $2^{S}$ in $(Z / p)^{\times}$ ).

Initialise $r = a^{(Q + 1) /2}$ , $t = a^{Q}$ , $c = z^{Q}$ , $m = S$ . Loop invariants:

$r^{2} = a \cdot t$ (so $r^{2} \equiv a$ holds when $t = 1$ ).
$t$ is a $2^{m}$ -th root of unity in $(Z / p)^{\times}$ .
$c$ is a primitive $2^{m}$ -th root of unity (an order- $2^{m}$ element).

Initial verification: $r^{2} = a^{Q + 1} = a \cdot a^{Q} = a \cdot t$ ✓. $t^{2^{S}} = a^{Q \cdot 2^{S}} = a^{p - 1} = 1$ ✓. $c$ has order $2^{S}$ ✓.

At each iteration: find the smallest $i \in {0, 1, \dots, m - 1}$ with $t^{2^{i}} = 1$ ; if $i = 0$ then $t = 1$ and the algorithm terminates with $r$ as the answer. Otherwise $i < m$ (since $t$ is a $2^{m}$ -th but not a $2^{0}$ -th root). Set $b = c^{2^{m - i - 1}}$ , so $b^{2^{i + 1}} = c^{2^{m}} = 1$ and $b^{2^{i}} = c^{2^{m - 1}} = - 1$ (since $c$ has order $2^{m}$ and $c^{2^{m - 1}}$ is the unique order- $2$ element). Update $r \mapsto r b$ , $t \mapsto t b^{2}$ , $c \mapsto b^{2}$ , $m \mapsto i$ .

Invariant preservation: $(r b)^{2} = r^{2} b^{2} = a t b^{2} = a (t b^{2})$ ✓. $(t b^{2})^{2^{i}} = t^{2^{i}} b^{2^{i + 1}} = 1 \cdot 1 = 1$ ✓. $b^{2} = c^{2^{m - i}}$ has order $2^{i}$ ✓.

The loop terminates because $m$ strictly decreases at each iteration. When $m = 0$ , $t$ is a $2^{0} = 1$ -th root of unity, so $t = 1$ , and the algorithm exits with $r^{2} = a$ . Number of iterations is at most $S$ ; total cost is $O ((lo g p)^{2} + (lo g p) S^{2})$ multiplications modulo $p$ . $□$

Connections Master

Primitive roots and structure of $(Z / n)^{\times}$ 21.01.05. Just shipped. The cyclicity of $(Z / p)^{\times}$ proved in 21.01.05 supplies the operative tool for Euler's criterion: the order- $2$ element $- 1$ is exactly $g^{(p - 1) /2}$ for any primitive root $g$ , and the index- $2$ subgroup of squares is the kernel of the unique order- $2$ character. The discrete-logarithm framework of 21.01.05 gives the explicit identification $a \in QR_{p}$ iff $ind_{g} (a)$ is even. The Tonelli-Shanks algorithm (Theorem 5) uses the discrete-logarithm structure indirectly via the $2$ -Sylow subgroup of $(Z / p)^{\times}$ generated by $z^{Q}$ .
Fermat-Euler-Wilson theorems 21.01.04. Shipped. Euler's criterion is a refinement of Fermat: Fermat says $a^{p - 1} \equiv 1 (mod p)$ for $a$ coprime to $p$ , and Euler's criterion sharpens this by computing $a^{(p - 1) /2}$ — the unique square root of $1$ in $F_{p}$ accessible to $a$ — to detect quadratic-residue status. The first supplementary law $(- 1/ p) = + 1$ iff $p \equiv 1 (mod 4)$ characterises the primes expressible as sums of two squares (Fermat 1640, Euler 1755), one of the canonical applications of 21.01.04.
Congruences and CRT 21.01.03. Shipped. The Jacobi symbol $(a / n) = \prod_{p} (a / p)^{e_{p}}$ is defined by CRT-decomposing $(Z / n)^{\times} ≅ \prod_{p} (Z / p^{e_{p}})^{\times}$ and taking the product of Legendre symbols. The Goldwasser-Micali encryption scheme (Theorem 6) uses CRT decomposition $Z / n ≅ Z / p \times Z / q$ to detect quadratic residuosity modulo $n = pq$ via separate Legendre-symbol tests modulo $p$ and modulo $q$ — the secret-key advantage that gives semantic security.
Quadratic reciprocity and Gauss sums 21.01.07. Pending. The main theorem of which the present unit is the setting: for distinct odd primes $p, q$ , $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . The full proof — Gauss's first proof by induction (1796/1801), Eisenstein's lattice-point proof (1844), Dirichlet's Gauss-sum proof (1854) — is deferred to 21.01.07. The present unit supplies all the operative tools: the Legendre symbol, Euler's criterion, multiplicativity, the two supplementary laws, and Gauss's lemma. 21.01.07 adds the reciprocity-law proof and the Jacobi-symbol generalisation.
Riemann zeta function $ζ (s)$ 21.03.01. Shipped. The quadratic-character framework lifts to Dirichlet $L$ -functions $L (s, χ)$ associated to characters $χ$ of $(Z / n)^{\times}$ for various $n$ . The Legendre symbol $a \mapsto (a / p)$ extends to the quadratic Dirichlet character $χ_{p} : (Z / p)^{\times} \to C^{\times}$ (taking values $\pm 1$ ), and the Dirichlet $L$ -function $L (s, χ_{p}) = \sum_{n} χ_{p} (n) n^{- s}$ has functional equation and Euler product that mirror $ζ (s)$ — Dirichlet 1837 Werke I proved $L (1, χ) \neq = 0$ for non-principal $χ$ to deduce the infinitude of primes in arithmetic progressions. The quadratic Dirichlet $L$ -functions are the simplest non-principal twists of $ζ (s)$ and the prototype for the entire Dirichlet $L$ -function theory.
$p$ -adic numbers and Hensel's lemma 21.02.07. Pending. The square-root question modulo $p$ extends to modulo $p^{k}$ and ultimately to the $p$ -adic integers $Z_{p}$ . Hensel's lemma: if $a$ is a quadratic residue modulo $p$ (with $p$ odd) and $f (x) = x^{2} - a$ , then for any solution $r_{0}$ modulo $p$ , there exists a unique lift $r \in Z_{p}$ with $r \equiv r_{0} (mod p)$ and $r^{2} = a$ in $Z_{p}$ . The case $p = 2$ requires the more delicate Hensel condition $a \equiv 1 (mod 8)$ for $a$ to be a square in $Z_{2}$ . The Hilbert symbol $(a, b)_{p}$ (Theorem 7) is the $p$ -adic completion of the Legendre symbol, with the product formula $\prod_{v} (a, b)_{v} = 1$ encoding quadratic reciprocity adelically.

Historical & philosophical context Master

Euler 1744 Comm. Acad. Petrop. 14, 151-181 ^{[Euler 1744]} is the originator of quadratic reciprocity in the disguised form of theorems about divisors of binary quadratic forms $p a^{2} + q b^{2}$ . Euler observed empirically that the set of prime divisors of $a^{2} - q$ depends only on the residue class of the prime modulo $4 q$ — a statement equivalent to quadratic reciprocity once translated through the Legendre-symbol formalism (not available to Euler). Continued in Euler 1783 Opera Postuma I, 64-84, which contains the cleanest formulation Euler attained.

Legendre 1798 Essai sur la théorie des nombres ^{[Legendre 1798]} introduced the symbol $(a / p)$ that bears his name and gave the modern formulation of the reciprocity law: for distinct odd primes $p, q$ , $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . Legendre's proof is incomplete: it depends on the unproven assumption that for every residue class $a (mod m)$ coprime to $m$ , there exist infinitely many primes $p \equiv a (mod m)$ — a statement equivalent to Dirichlet's theorem on primes in arithmetic progressions, not proved until Dirichlet 1837 Werke I via the analytic non-vanishing $L (1, χ) \neq = 0$ for non-principal Dirichlet characters. So Legendre had the right statement but no complete proof.

Gauss 1801 Disquisitiones Arithmeticae arts. 125-152 ^{[Gauss 1801]} gave the first complete proof. Gauss had discovered the law independently in April 1796 (mathematical diary entry of 19 April 1796: "Per inductionem inveni 24 Mart. 1796: ..." — "By induction I discovered on March 24, 1796: ..."), as a 19-year-old, and called it the theorema aureum — "the golden theorem" — or the fundamental theorem of arithmetic in his later writings. Gauss produced eight independent proofs over his lifetime, six appearing in Werke II 1863: the induction proof (1801), the Gauss-sum proof (1811 unpublished, 1818 published), the lemma-and-permutation proof (1818), the cyclotomic proof (1818), and three more in the Nachlass. Gauss's intent in proving the law eight times was to find the conceptually right proof — and the multiplicity of methods is itself a signal that the law sits at a deep junction of arithmetic, geometry, and analysis. Today more than $300$ independent proofs are known, catalogued in Lemmermeyer 2000 Reciprocity Laws.

Jacobi 1837 J. reine angew. Math. 30, 166-182 ^{[Jacobi 1837]} extended the Legendre symbol to the Jacobi symbol $(a / n)$ for $n$ odd positive composite, by multiplicativity in the prime-power decomposition. The Jacobi symbol satisfies the same reciprocity law $(m / n) (n / m) = (- 1)^{((m - 1) /2) ((n - 1) /2)}$ for $m, n$ odd coprime positive, and the same two supplementary laws. The algorithmic consequence is the binary Jacobi-symbol algorithm: compute $(a / n)$ in $O ((lo g n)^{2})$ time by alternating reduction $a mod n$ and reciprocity flip, without factoring $n$ — the algorithm used in every modern cryptographic library.

Eisenstein 1844 J. reine angew. Math. 27, 289-310 ^{[Eisenstein 1844]} proved cubic reciprocity in the cyclotomic ring $Z [ζ_{3}]$ of Eisenstein integers; the companion paper in Crelle 28 gave biquadratic reciprocity in $Z [i]$ . Eisenstein's 1847 Crelle 35 paper gave the lattice-point-counting proof of quadratic reciprocity that became the standard textbook proof: count integer points strictly under the line of slope $q / p$ inside the rectangle $[1, (p - 1) /2] \times [1, (q - 1) /2]$ , and observe that the total point count modulo $2$ equals $((p - 1) /2) ((q - 1) /2) mod 2$ by counting two ways.

Hilbert 1897 Jahresber. DMV 4, 175-546 ^{[Hilbert 1897]} — the Zahlbericht, Hilbert's encyclopaedic report on algebraic number theory — developed the Hilbert symbol $(a, b)_{v}$ at each place $v$ of a number field and the product formula $\prod_{v} (a, b)_{v} = 1$ . The Hilbert symbol at a finite prime detects whether $Z^{2} - a X^{2} - b Y^{2}$ has non-zero solutions over the local field; quadratic reciprocity becomes the Euler-factor matching of the product formula. Hilbert's 9th problem (1900 ICM Paris) asks for the most general reciprocity law in any algebraic number field — the question answered by Takagi 1920 and Artin 1927.

Takagi 1920 J. Coll. Sci. Tokyo 41, 1-133 ^{[Takagi 1920]} proved class field theory for relatively abelian extensions of number fields: every finite abelian extension $L / K$ corresponds bijectively to a generalised ideal class group of $K$ , with the conductor-discriminant formula expressing the abelian $L$ -function as a product of Hecke $L$ -functions. Specialised to $K = Q$ and quadratic $L = Q (d)$ , Takagi's theorem reduces to quadratic reciprocity. Artin 1927 Hamb. Abh. 5, 353-363 ^{[Artin 1927]} added the explicit Frobenius-isomorphism formulation — the Artin reciprocity law — identifying the Artin map $I_{K} (m) / P_{L / K} (m) \sim Gal (L / K)$ as the canonical isomorphism. The non-abelian generalisation is the Langlands programme: Artin reciprocity equals abelian Langlands; the Langlands functoriality conjectures (Langlands 1967 letter to Weil, Langlands 1970 Yale Lectures) extend to all reductive groups via $L$ -functions of automorphic representations.

The applied legacy: Tonelli 1891 Göttinger Nachr. ^{[Tonelli 1891]} and Shanks 1972 Proc. Manitoba ^{[Shanks 1972]} gave the deterministic modular-square-root algorithm used in elliptic-curve point decompression — every ECDSA verification, every Ed25519 signature check. Goldwasser-Micali 1982 STOC ^{[Goldwasser-Micali 1982]} founded the modern provable-security paradigm with the first semantically-secure encryption scheme from the quadratic-residuosity assumption. The quadratic sieve of Pomerance 1985 Lecture Notes Math. 1122 — the second-fastest classical integer-factorisation algorithm, with sub-exponential complexity $L_{n} [1/2, c]$ — finds smooth values of $f (x) = x^{2} - n$ to build a non-degenerate congruence of squares $x^{2} \equiv y^{2} (mod n)$ from which $g cd (x - y, n)$ factors $n$ . The same quadratic-residue framework Gauss developed in 1801 underlies every modern cryptographic protocol involving modular square roots.

Bibliography Master

@article{Euler1744,
  author  = {Euler, Leonhard},
  title   = {Theoremata circa divisores numerorum in hac forma $p a^2 + q b^2$ contentorum},
  journal = {Commentarii Academiae Scientiarum Imperialis Petropolitanae},
  volume  = {14},
  pages   = {151--181},
  year    = {1744},
  note    = {The originator paper conjecturing special cases of quadratic reciprocity in the disguised form of theorems about prime divisors of binary quadratic forms $p a^2 + q b^2$. Continued in Euler 1783 *Opera Postuma* I, 64-84.}
}

@book{Legendre1798,
  author    = {Legendre, Adrien-Marie},
  title     = {Essai sur la th{\'e}orie des nombres},
  publisher = {Duprat},
  address   = {Paris},
  year      = {1798},
  note      = {First statement of the law of quadratic reciprocity in the modern symbol form. The Legendre symbol $(a/p)$ is introduced as a convenient notation. The proof depends on the unproven Dirichlet theorem on primes in arithmetic progressions and is therefore incomplete.}
}

@book{Gauss1801,
  author    = {Gauss, Carl Friedrich},
  title     = {Disquisitiones Arithmeticae},
  publisher = {Gerhard Fleischer},
  address   = {Leipzig},
  year      = {1801},
  note      = {Articles 95-152 are the canonical originator development of quadratic residues, the Legendre symbol, Euler's criterion, Gauss's lemma, the two supplementary laws, and the first complete proof of quadratic reciprocity (the theorema aureum). Gauss produced eight independent proofs over his lifetime; six appear in *Werke* II 1863. English translation by Arthur A. Clarke, Yale University Press, 1965/1986.}
}

@article{Jacobi1837,
  author  = {Jacobi, Carl Gustav Jacob},
  title   = {{\"U}ber die Kreistheilung und ihre Anwendung auf die Zahlentheorie},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {30},
  pages   = {166--182},
  year    = {1837},
  note    = {Introduces the Jacobi symbol $(a/n)$ for $n$ odd positive composite, with the same reciprocity law and two supplementary laws as the Legendre symbol. Enables the binary $O((\log n)^2)$-time algorithm for computing the Legendre/Jacobi symbol without factoring.}
}

@article{Eisenstein1844,
  author  = {Eisenstein, Gotthold},
  title   = {Beweis des Reciprocit{\"a}tssatzes f{\"u}r die cubischen Reste in der Theorie der aus den dritten Wurzeln der Einheit zusammengesetzten complexen Zahlen},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {27},
  pages   = {289--310},
  year    = {1844},
  note    = {Cubic reciprocity in the cyclotomic ring $\mathbb{Z}[\zeta_3]$ of Eisenstein integers. Companion paper *Crelle* 28 (1844) gives biquadratic reciprocity in $\mathbb{Z}[i]$. Eisenstein 1847 *Crelle* 35 added the lattice-point-counting proof of quadratic reciprocity that became the standard textbook proof.}
}

@article{Hilbert1897,
  author  = {Hilbert, David},
  title   = {Die Theorie der algebraischen Zahlk{\"o}rper},
  journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
  volume  = {4},
  pages   = {175--546},
  year    = {1897},
  note    = {The *Zahlbericht* — Hilbert's encyclopaedic report on algebraic number theory. Develops the Hilbert symbol $(a, b)_v$ at each place of a number field and the product formula $\prod_v (a, b)_v = 1$. Hilbert's 9th problem (1900 ICM Paris) asks for the most general reciprocity law in any algebraic number field.}
}

@article{Takagi1920,
  author  = {Takagi, Teiji},
  title   = {{\"U}ber eine Theorie des relativ-Abelschen Zahlk{\"o}rpers},
  journal = {Journal of the College of Science, Tokyo},
  volume  = {41},
  pages   = {1--133},
  year    = {1920},
  note    = {Class field theory for relatively abelian extensions of number fields. Every finite abelian extension corresponds bijectively to a generalised ideal class group via the Artin map.}
}

@article{Artin1927,
  author  = {Artin, Emil},
  title   = {Beweis des allgemeinen Reziprozit{\"a}tsgesetzes},
  journal = {Abhandlungen aus dem Mathematischen Seminar der Universit{\"a}t Hamburg},
  volume  = {5},
  pages   = {353--363},
  year    = {1927},
  note    = {Artin reciprocity. The Artin map induces an isomorphism from generalised ideal classes to the Galois group, sending a prime $\mathfrak{p}$ to its Frobenius element. The modern formulation of all reciprocity laws for abelian extensions; the non-abelian generalisation is the Langlands programme.}
}

@article{Tonelli1891,
  author  = {Tonelli, Alberto},
  title   = {Bemerkung {\"u}ber die Aufl{\"o}sung quadratischer Congruenzen},
  journal = {Nachrichten von der K{\"o}niglichen Gesellschaft der Wissenschaften zu G{\"o}ttingen},
  year    = {1891},
  pages   = {344--346},
  note    = {The first deterministic algorithm for computing square roots modulo a prime $p$.}
}

@inproceedings{Shanks1972,
  author    = {Shanks, Daniel},
  title     = {Five number-theoretic algorithms},
  booktitle = {Proceedings of the Second Manitoba Conference on Numerical Mathematics},
  address   = {Winnipeg},
  pages     = {51--70},
  year      = {1972},
  note      = {Tonelli-Shanks algorithm for modular square roots. The standard algorithm in cryptographic libraries for elliptic-curve point decompression.}
}

@inproceedings{GoldwasserMicali1982,
  author    = {Goldwasser, Shafi and Micali, Silvio},
  title     = {Probabilistic encryption and how to play mental poker keeping secret all partial information},
  booktitle = {Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {365--377},
  year      = {1982},
  note      = {Refined in *Journal of Computer and System Sciences* 28 (1984), 270-299. The first semantically secure public-key encryption scheme, founded on the quadratic-residuosity assumption. The founding example of the modern provable-security paradigm.}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman. Chapters V-VII develop quadratic residues, the Legendre symbol, Gauss's lemma, the supplementary laws, the law of quadratic reciprocity, and the Jacobi symbol.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990},
  note      = {Chapter 5 develops the Legendre symbol, Euler's criterion, Gauss's lemma, and the supplementary laws. Chapter 6 proves quadratic reciprocity via Gauss sums.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976},
  note      = {Chapter 9 develops quadratic residues, the Legendre symbol, and the Jacobi symbol with the analytic perspective. Includes the Gauss-sum derivation of quadratic reciprocity.}
}

@book{Burton2010,
  author    = {Burton, David M.},
  title     = {Elementary Number Theory},
  edition   = {7},
  publisher = {McGraw-Hill},
  year      = {2010},
  note      = {Chapter 9 develops quadratic residues, the Legendre symbol, and Euler's criterion at the undergraduate Beginner-tier level, with explicit residue tables for small primes.}
}

@book{Cox2013,
  author    = {Cox, David A.},
  title     = {Primes of the form $x^2 + n y^2$: Fermat, class field theory, and complex multiplication},
  edition   = {2},
  publisher = {Wiley},
  year      = {2013},
  note      = {The canonical modern textbook on quadratic reciprocity and its consequences for Fermat-style 'primes of the form' problems, with the entire originator chain Fermat-Euler-Lagrange-Legendre-Gauss developed from primary sources.}
}

@book{Lemmermeyer2000,
  author    = {Lemmermeyer, Franz},
  title     = {Reciprocity Laws: From Euler to Eisenstein},
  series    = {Springer Monographs in Mathematics},
  publisher = {Springer},
  year      = {2000},
  note      = {Catalogue of more than $300$ independent proofs of quadratic reciprocity, with the historical development from Euler 1744 to Eisenstein 1844 traced in primary-source detail.}
}

Prerequisites

21.01.03
21.01.04
21.01.05

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §9 (quadratic residues, the Legendre symbol, Euler's criterion, with worked tables modulo small primes); Khan Academy 'Modular arithmetic' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §5 (Legendre symbol, Euler's criterion, Gauss's lemma, the two supplementary laws, statement of quadratic reciprocity); Apostol 1976 *Introduction to Analytic Number Theory* §9
master: Gauss 1801 *Disquisitiones Arithmeticae* arts. 95-152 (originator: quadratic residues, Legendre symbol, Euler's criterion, Gauss's lemma, the first complete proof of quadratic reciprocity, the theorema aureum); Euler 1744 *Comm. Acad. Petrop.* 14, 151-181 (special-case conjectures of reciprocity for divisors of $p a^2 + q b^2$); Legendre 1798 *Essai sur la théorie des nombres* (statement of the law and partial proof); Jacobi 1837 *J. reine angew. Math.* 30, 166-182 (Jacobi symbol $(a/n)$ for $n$ odd composite, reciprocity for the Jacobi symbol); Eisenstein 1844 *J. reine angew. Math.* 27, 289-310 (cubic and biquadratic reciprocity, lattice-point counting proof of quadratic reciprocity); Hilbert 1897 *Jahresber. DMV* 4, 175-546 (Hilbert reciprocity, general reciprocity in the *Zahlbericht*); Takagi 1920 *J. Coll. Sci. Tokyo* 41, 1-133 (class field theory for relatively abelian number fields); Artin 1927 *Hamb. Abh.* 5, 353-363 (Artin reciprocity, modern formulation of general reciprocity for abelian extensions); Tonelli 1891 *Göttinger Nachr.* 1891, 344-346 (square roots modulo $p$); Shanks 1972 *Proc. Second Manitoba Conf. Numer. Math.* 51-70 (Tonelli-Shanks algorithm); Goldwasser-Micali 1982 *STOC* 365-377 (probabilistic encryption from quadratic-residuosity); Hardy-Wright 2008 6e §§V-VII

References

Euler, L. — Theoremata circa divisores numerorum · *Commentarii Academiae Scientiarum Imperialis Petropolitanae* 14 (1744), 151-181. The paper that first conjectured special cases of quadratic reciprocity in the disguised form of theorems about divisors of $p a^2 + q b^2$. Euler stated, for prime divisors of $a^2 - q$, that the splitting behaviour depends only on the residue class of the divisor modulo $4q$ — equivalent to the statement of quadratic reciprocity once translated through the Legendre-symbol formalism (not available to Euler). Continued in Euler 1783 *Opera Postuma* I, 64-84 ('Observationes circa divisionem quadratorum per numeros primos').
Legendre, A.-M. — Essai sur la théorie des nombres · Duprat, Paris, 1798 (1st edition); 2nd edition 1808; 3rd edition (greatly expanded) 1830 *Théorie des nombres*. The first publication of the law of quadratic reciprocity in the modern symbol form $(p/q)(q/p) = (-1)^{((p-1)/2)((q-1)/2)}$ for odd primes $p, q$, together with the two supplementary laws for $(-1/p)$ and $(2/p)$. Legendre's proof is incomplete: it depends on an unproven assumption equivalent to Dirichlet's theorem on primes in arithmetic progressions, which Dirichlet did not prove until 1837. The Legendre symbol $(a/p) \in \{-1, 0, +1\}$ is introduced as a convenient notation; the modern multiplicative property $(ab/p) = (a/p)(b/p)$ is recorded as Theorem VI.
Gauss, C. F. — Disquisitiones Arithmeticae · Leipzig: Gerhard Fleischer, 1801. Articles 95-152 are the canonical originator development of the quadratic-residue theory and the first complete proof of quadratic reciprocity (Gauss's first proof, by induction on the larger prime, completed April 1796 according to Gauss's mathematical diary). Article 95: definition of quadratic residue (residuum) and non-residue (non-residuum) modulo a prime. Articles 96-105: Euler's criterion, the multiplicative property, and counting (exactly half of the nonzero residues are squares). Articles 106-124: Gauss's lemma (article 106) and the two supplementary laws (articles 108-114 for $(-1/p)$, articles 112-114 for $(2/p)$). Articles 125-152: the theorema aureum, with the first proof by induction (articles 135-145). Gauss called the law 'the gem of arithmetic' and produced eight independent proofs over his lifetime, six appearing in *Werke* II. English translation by Arthur A. Clarke, Yale UP 1965 / 1986 corrected reprint.
Jacobi, C. G. J. — Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie · *Journal für die reine und angewandte Mathematik* 30 (1837), 166-182. Introduces the **Jacobi symbol** $(a/n)$ for $n$ odd positive composite, defined as $\prod_i (a/p_i)^{e_i}$ where $n = \prod p_i^{e_i}$ is the prime factorisation. Theorem: the Jacobi symbol satisfies the same multiplicative property $(a/n)(b/n) = (ab/n)$ and the same reciprocity law $(m/n)(n/m) = (-1)^{((m-1)/2)((n-1)/2)}$ for $m, n$ odd coprime positive. The Jacobi symbol enables the modern $O((\log n)^2)$-time algorithm for computing the Legendre symbol without factoring (by repeated reciprocity steps, halving the larger argument).
Eisenstein, G. — Beweis des Reciprocitätssatzes für die cubischen Reste · *Journal für die reine und angewandte Mathematik* 27 (1844), 289-310. Eisenstein's cubic-reciprocity proof, in the cyclotomic ring $\mathbb{Z}[\zeta_3]$ of Eisenstein integers. Companion paper 28 (1844) gives biquadratic reciprocity in $\mathbb{Z}[i]$. Eisenstein later (Crelle 35, 1847) gave a lattice-point-counting proof of quadratic reciprocity that became the standard textbook proof — counting integer points under a line of slope $q/p$ inside the rectangle $[1, (p-1)/2] \times [1, (q-1)/2]$.
Hilbert, D. — Die Theorie der algebraischen Zahlkörper (Zahlbericht) · *Jahresbericht der Deutschen Mathematiker-Vereinigung* 4 (1897), 175-546. The *Zahlbericht* — Hilbert's encyclopaedic report on algebraic number theory commissioned by the DMV in 1893. Part IV §§64-90 develops Hilbert's general reciprocity formula via the **Hilbert symbol** $(a, b)_p \in \{\pm 1\}$ at each place $p$ of $\mathbb{Q}$, with the product formula $\prod_p (a, b)_p = 1$ over all places (finite and infinite). The Hilbert symbol at a finite place $p$ for $a, b \in \mathbb{Q}_p^\times$ records whether $a x^2 + b y^2 = z^2$ has a non-zero solution in $\mathbb{Q}_p$; quadratic reciprocity is equivalent to the product formula by Euler-factor matching. Hilbert's *Problems* (1900 ICM Paris) ninth problem asks for the most general reciprocity law in any algebraic number field — the question answered by Takagi 1920 and Artin 1927.
Takagi, T. — Über eine Theorie des relativ-Abelschen Zahlkörpers · *Journal of the College of Science, Tokyo* 41 (1920), 1-133. Takagi's class field theory: every finite abelian extension $L/K$ of a number field $K$ corresponds bijectively to a generalised ideal class group of $K$ via the Artin map; the conductor-discriminant formula expresses the abelian $L$-function as a product of Hecke $L$-functions. Specialised to $K = \mathbb{Q}$ and quadratic extensions $L = \mathbb{Q}(\sqrt{d})$, Takagi's theorem reduces to quadratic reciprocity. Takagi's monograph *Daisuteki seisuron* (Algebraic Number Theory, Iwanami, 1948) is the standard exposition.
Artin, E. — Beweis des allgemeinen Reziprozitätsgesetzes · *Hamburger Abhandlungen* 5 (1927), 353-363. Artin reciprocity: for $L/K$ finite abelian, the **Artin map** $\mathrm{Art}_{L/K} : I_K(\mathfrak{m}) / P_{L/K}(\mathfrak{m}) \to \mathrm{Gal}(L/K)$ from generalised ideal classes (modulo a conductor $\mathfrak{m}$) to the Galois group is an isomorphism. The modern formulation of all reciprocity laws for abelian extensions of number fields, identifying the global Artin reciprocity with the splitting behaviour of primes. Specialises to quadratic reciprocity for the quadratic extension $\mathbb{Q}(\sqrt{p^*})/\mathbb{Q}$ where $p^* = (-1)^{(p-1)/2} p$ is the signed prime, with the Frobenius element at $q$ acting by $(p^*/q)$.
Tonelli, A. — Bemerkung über die Auflösung quadratischer Congruenzen · *Göttinger Nachrichten* 1891, 344-346. The first deterministic algorithm for computing square roots modulo a prime $p$: given $a$ with $(a/p) = 1$, find $r$ with $r^2 \equiv a \pmod p$. Tonelli's algorithm runs in $O((\log p)^4)$ time. Shanks 1972 *Proc. Second Manitoba Conf. Numer. Math.* 51-70 refined this to $O((\log p)^2 + (\log p) S^2)$ where $2^S \| p - 1$; the combined Tonelli-Shanks method is the standard modular-square-root algorithm in cryptographic libraries (OpenSSL, libgmp, Crypto++).
Shanks, D. — Five number-theoretic algorithms · *Proceedings of the Second Manitoba Conference on Numerical Mathematics* (Winnipeg, 1972), 51-70. Shanks's modular-square-root algorithm: given a quadratic residue $a$ modulo a prime $p$ with $p - 1 = 2^S Q$ ($Q$ odd), find a non-residue $z$ modulo $p$, and combine $a^{(Q + 1)/2}$ with the cyclic subgroup of $2^S$-th roots of unity generated by $z^Q$ to construct $\sqrt a$. Average complexity $O((\log p)^2)$ multiplications for random $p$; worst case dominated by the $2$-adic valuation of $p - 1$.
Goldwasser, S. and Micali, S. — Probabilistic encryption and how to play mental poker keeping secret all partial information · *Proceedings of the 14th Annual ACM Symposium on Theory of Computing* (STOC 1982), 365-377. Refined in *Journal of Computer and System Sciences* 28 (1984), 270-299. The first **semantically secure** public-key encryption scheme. Public key: $n = pq$ (RSA modulus) and a quadratic non-residue $y$ modulo $n$ with Jacobi symbol $+1$. Encryption of bit $b$: random $r \in (\mathbb{Z}/n)^\times$, ciphertext $c = y^b r^2 \bmod n$. Decryption uses the secret factorisation $n = pq$ to test $(c/p)$. Security: indistinguishability under chosen-plaintext attack from the **quadratic-residuosity assumption** — distinguishing pseudosquares from squares modulo $n$ is computationally hard. Founded the modern provable-security framework.
Hardy, G. H. and Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapters V-VII develop quadratic residues, the Legendre symbol, Gauss's lemma, the supplementary laws, the law of quadratic reciprocity (with two proofs: Gauss's lemma + Eisenstein lattice-point counting), and the Jacobi symbol. Chapter VI §6.10 gives the historical timeline from Fermat to Euler to Gauss. The canonical undergraduate reference.
Ireland, K. and Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990), §5. Modern group-theoretic development: $(\mathbb{Z}/p)^\times$ cyclic, squaring map has index $2$, Legendre symbol as a character $(\mathbb{Z}/p)^\times \to \{\pm 1\}$, Euler's criterion as evaluating the character via the unique order-$2$ element. The standard graduate-text reference, with the proof of quadratic reciprocity via Gauss sums (§6) as preparation for the higher-reciprocity laws.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics, 1976. §9 develops quadratic residues and the Legendre symbol with the analytic perspective. Apostol gives a careful Gauss-sum derivation of quadratic reciprocity and connects the Legendre symbol to Dirichlet characters via the Kronecker symbol extension. The treatment of computational aspects (the binary Jacobi-symbol algorithm) is in §9.7.
Cox, D. A. — Primes of the form $x^2 + n y^2$ · Wiley, 2nd edition (2013). The canonical modern textbook on quadratic reciprocity and its consequences for Fermat-style 'primes of the form' problems. Chapter 1 develops the entire originator chain Fermat-Euler-Lagrange-Legendre-Gauss with primary-source citations. Chapter 4 is the modern class-field-theoretic perspective via the Hilbert class field. Chapter 5 connects to ring class fields and complex multiplication, the bridge to elliptic-curve cryptography.

Estimated time

beginner: 18m
intermediate: 45m
master: 80m