Quadratic Reciprocity, From the Ground Up

A self-contained course for the Map of Math project. Prerequisites: §3 (algebra foundations) of elliptic-curves-course.md for group basics — not repeated here. Canonical connections graph: map-index.md.

How this doc fits the map

This thread started as a side question inside the elliptic curves course: point-counting on $E(\mathbb{F}_p)$ turned out to be built directly from Legendre symbols, and the splitting behavior of an elliptic curve’s 2-torsion turned out to be governed by whether the curve’s discriminant is a quadratic residue. That’s a real, load-bearing connection, not a coincidence of vocabulary — which is exactly why this earned its own course instead of a footnote. But quadratic reciprocity does not need elliptic curves to justify itself: it is one of the oldest, most re-proved, and most consequential theorems in number theory in its own right, and Gauss’s obsession with it (six proofs in his lifetime, two more found in his papers after his death) is a good signal of how much is packed into a statement that looks, at first glance, like a curiosity about squares.

Structure: motivation, then history, then the minimum number-theoretic machinery, then six coursework modules (each with a computer-verified worked example and a problem set), an answer key, resources, and — deliberately — no embedded connection graph. That now lives centrally in map-index.md, so this doc doesn’t drift out of sync with the elliptic curves doc or whatever comes next.

1. Motivation

Here is the question this whole course answers: given a prime $p$ and an integer $a$, does the congruence $x^2 \equiv a \;(\mathrm{mod}\;p)$ have a solution?

That sounds like it should be a local, one-off question — check $p$, check $a$, done. The surprise, and the reason Gauss called this his “golden theorem” (theorema aureum), is that the answer for a given prime $q$ playing the role of $a$ turns out to be governed by an unexpectedly clean, symmetric relationship between $p$ and $q$ themselves — not by any deep property of either prime individually. Once you have that relationship, you can decide solvability of $x^2 \equiv q \;(\mathrm{mod}\;p)$ for huge $p$ and $q$ without factoring anything and without checking all $\frac{p-1}{2}$ candidates by brute force — you just play a Euclidean-algorithm-like game flipping the roles of $p$ and $q$ back and forth. That efficiency is not a minor convenience; it is the difference between a question that is computationally trivial and one that would otherwise require exponential search.

Three reasons this specific theorem earns a permanent, well-built thread in your map, distinct from being just a stepping stone to something else:

It is the smallest member of a very long, very deep family. “Is $a$ an $n$-th power mod $p$?” for $n=2$ is quadratic reciprocity; for $n=3$ it’s cubic reciprocity (Gauss, Eisenstein — needs the Eisenstein integers); for $n=4$ it’s biquadratic reciprocity (Gauss — needs the Gaussian integers); Kummer’s 19th-century attempts to find higher reciprocity laws for general $n$ (motivated in part by Fermat’s Last Theorem) are what led him to invent “ideal numbers,” the ancestor of ideals in ring theory. The entire program culminates in Artin reciprocity (1927) — the full abelian generalization via class field theory — and, beyond that, in the still-open Langlands program, which conjectures the correct non-abelian generalization. The modularity theorem that resolves Fermat’s Last Theorem (see the elliptic curves course, Modules 6–7) is, in this framing, literally a reciprocity law — just for a 2-dimensional Galois representation instead of the 1-dimensional one quadratic reciprocity handles. Studying quadratic reciprocity properly is studying the first, fully-solved rung of a ladder that current research mathematics is still climbing.

It is a genuine hub, just like elliptic curves, but on the “purely arithmetic” side of the map. It touches primality testing, the representability of integers by quadratic forms (which primes are sums of two squares? which are $x^2+5y^2$?), the structure of finite fields, and — as you found — the arithmetic of elliptic curves via 2-torsion. Where the elliptic curve thread was a hub connecting geometry, analysis, and arithmetic, this thread is a hub within arithmetic itself, connecting elementary number theory outward to algebraic number theory and class field theory.

It is short enough to fully master, and its proof is genuinely enlightening. Unlike many deep theorems where the proof is a slog that teaches you little beyond the statement, the classical lattice-point proof of quadratic reciprocity (Module 4) is a self-contained, beautiful piece of combinatorial geometry you can carry out by hand on a napkin, and it directly explains why the symmetric relationship between $p$ and $q$ has to hold — it isn’t magic once you’ve drawn the picture.

2. History

Sources consulted: Quadratic reciprocity — Wikipedia, Artin reciprocity — Wikipedia, Proofs of quadratic reciprocity — Wikipedia/HandWiki, Robin Chapman’s exposition of Eisenstein’s proof.

3. Minimum machinery

You already have groups, rings, and fields from the elliptic curves course (§3 there). Two additional facts specific to this thread:

The group $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of order $p-1$. This is a nontrivial fact (it follows from the theory of finite fields: a finite subgroup of the multiplicative group of any field is cyclic), but you can take it as given here. A generator of this group is called a primitive root mod $p$.

Quadratic residues are exactly the index-2 subgroup. Since $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic of even order $p-1$, it has a unique subgroup of index 2 — the elements that are even powers of a fixed primitive root $g$. Squaring is the group homomorphism $x \mapsto x^2$, with kernel $\{1,-1\}$ (order 2) and image exactly this index-2 subgroup. So “the quadratic residues mod $p$” isn’t an ad hoc list — it is, on the nose, the unique subgroup of index 2 inside a cyclic group of even order. This is the cleanest way to see why exactly half of the nonzero residues are squares.

Worked example. Take $p=11$. Brute-force squares: $1^2,\dots,10^2 \bmod 11 = 1,4,9,5,3,3,5,9,4,1$, giving QR set $\{1,3,4,5,9\}$ — exactly 5 elements, half of the 10 nonzero residues, as expected. Independently: $g=2$ is a primitive root mod 11 (verified computationally: its powers $2,4,8,5,10,9,7,3,6,1$ hit all 10 nonzero residues before repeating). The even powers of 2 are $2^2,2^4,2^6,2^8,2^{10} = 4,5,9,3,1$ — exactly the same set $\{1,3,4,5,9\}$. The two descriptions (brute-force squaring, and “even powers of a primitive root”) agree, as the theory predicts.

4. Coursework

Module 1 — Euler’s criterion and the Legendre symbol

Objectives: define the Legendre symbol; prove and use Euler’s criterion; establish multiplicativity.

Exposition. For an odd prime $p$ and integer $a$ with $p \nmid a$, define the Legendre symbol $$\left(\frac{a}{p}\right) = \begin{cases} 1 & a \text{ is a quadratic residue mod } p \\ -1 & a \text{ is a quadratic non-residue mod } p\end{cases}$$ (and $\left(\frac{a}{p}\right) = 0$ if $p \mid a$). Euler’s criterion gives a computable formula: $$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \;(\mathrm{mod}\;p).$$ (Sketch of why: by Fermat’s little theorem $a^{p-1}\equiv 1$, so $a^{(p-1)/2} \equiv \pm 1$. If $a=x^2$, then $a^{(p-1)/2}=x^{p-1}\equiv1$. Conversely, using a primitive root $g$ with $a=g^k$, $a^{(p-1)/2}=g^{k(p-1)/2}$, which is $1$ exactly when $(p-1) \mid k(p-1)/2$, i.e. exactly when $k$ is even — matching “$a$ is a square” from §3.) An immediate, powerful consequence: the Legendre symbol is completely multiplicative, $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, because $(ab)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}$.

Worked example. $p=11$: is $7$ a QR mod 11? Euler’s criterion: $7^{5} \bmod 11$. Compute: $7^2=49\equiv5$, $7^4\equiv5^2=25\equiv3$, $7^5\equiv3\cdot7=21\equiv10\equiv-1 \;(\mathrm{mod}\;11)$. So $\left(\frac{7}{11}\right)=-1$ — confirmed against the brute-force QR set $\{1,3,4,5,9\}$ from §3, which does not contain 7. ✓ (Checked by computer against brute force for every $a,p$ with $p\in\{3,\dots,31\}$ — full agreement.)

Problem set 1. 1. Use Euler’s criterion to determine $\left(\frac{5}{13}\right)$ and $\left(\frac{6}{13}\right)$ by hand, then check that $\left(\frac{5}{13}\right)\cdot\left(\frac{6}{13}\right) = \left(\frac{30}{13}\right)$ (multiplicativity), computing the right-hand side independently. 2. Prove that $-1$ is a quadratic residue mod $p$ if and only if $p \equiv 1 \;(\mathrm{mod}\;4)$, directly from Euler’s criterion (this is the “first supplement” — you’ll use it constantly in Module 3). 3. Using the index-2-subgroup picture from §3, explain why the product of two non-residues is always a residue, and the product of a residue and a non-residue is always a non-residue, without invoking Euler’s criterion at all — purely from “residues form an index-2 subgroup.” 4. Why does the Legendre symbol require $p$ to be an odd prime specifically — where does the argument for Euler’s criterion break down if you try to define an analogous symbol mod a composite number?

Module 2 — Statement of the law

Objectives: state quadratic reciprocity and its two supplements precisely; use them together to evaluate symbols.

Exposition. 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}}.$$ In words: $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ agree, unless both $p$ and $q$ are $\equiv 3 \;(\mathrm{mod}\;4)$, in which case they disagree. Together with the two supplements, $$\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} \quad(\text{i.e. } 1 \text{ iff } p\equiv1\bmod4), \qquad \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}\quad(\text{i.e. } 1 \text{ iff } p\equiv\pm1\bmod8),$$ this is a complete algorithm: any Legendre symbol $\left(\frac{a}{p}\right)$ can be evaluated by factoring $a$ into $\pm 1$, powers of 2, and odd primes, then repeatedly flipping numerator and denominator via reciprocity — never needing to compute a single $(p-1)/2$-power directly. That algorithm is Module 3.

Worked example (verified against Euler’s criterion for all pairs of primes up to 37). $p=11,q=7$: both $\equiv 3\;(\mathrm{mod}\;4)$ ($11\equiv3$, $7\equiv3$), so the law predicts $\left(\frac{11}{7}\right) = -\left(\frac{7}{11}\right)$. Directly: $11\equiv4\;(\mathrm{mod}\;7)$, and $4=2^2$ is a QR mod 7, so $\left(\frac{11}{7}\right)=\left(\frac{4}{7}\right)=1$. Then the law predicts $\left(\frac{7}{11}\right)=-1$ — matching Module 1’s worked example exactly. ✓

Problem set 2. 1. Without computing any powers, use reciprocity plus the supplements to determine whether $x^2\equiv 3\;(\mathrm{mod}\;17)$ has a solution. 2. State (you don’t need to prove it) what $\left(\frac{-3}{p}\right)$ works out to in terms of $p \bmod 3$, by combining the two supplements’ style of reasoning with reciprocity applied to $q=3$; check your formula against $p=7,13,19$ directly by Euler’s criterion. 3. Verify computationally (or by hand for small cases) that the reciprocity law, applied twice ($p$ vs $q$, then $q$ vs $p$), is consistent — i.e. that it isn’t secretly asserting two different things depending on which prime you call $p$. 4. True or false, and justify: if $p\equiv1\;(\mathrm{mod}\;4)$, then $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ for every odd prime $q\ne p$. (Look carefully at what the exponent $\frac{p-1}{2}\cdot\frac{q-1}{2}$ mod 2 actually depends on.)

Module 3 — Computing symbols fast: the descent algorithm

Objectives: turn reciprocity + supplements into a Euclidean-algorithm-style computation; execute it on a nontrivial example.

Exposition. To compute $\left(\frac{a}{p}\right)$ for large $a,p$: repeatedly strip factors of 2 out of $a$ (applying the second supplement each time you strip one), then — once $a$ is odd — apply reciprocity to flip to $\left(\frac{p \bmod a}{a}\right)$ (with the appropriate sign from the reciprocity law, which only flips when both current numbers are $\equiv 3\;(\mathrm{mod}\;4)$), and repeat. This is exactly the Euclidean algorithm’s reduction pattern, and it terminates in $O(\log p)$ steps, just like $\gcd$ — dramatically faster than checking all $\frac{p-1}{2}$ residues by brute force, and it is precisely why the theorem is not just elegant but useful.

Worked example (computer-traced and verified against Euler’s criterion). Compute $\left(\frac{219}{383}\right)$ ($383$ is prime):

1. $219 \equiv 3$, $383\equiv3\;(\mathrm{mod}\;4)$ — both $\equiv3\bmod4$, so reciprocity flips sign. Running sign: $-1$. Swap: new pair $(383 \bmod 219, 219) = (164, 219)$.
2. Strip a factor of 2 from 164: $164 = 4\cdot41$ — that’s two factors of 2 (even count, second supplement doesn’t trigger), leaving odd part 41. Check flip: $41\equiv1\;(\mathrm{mod}\;4)$, so no sign flip regardless of $219\bmod4$. Swap: new pair $(219\bmod41, 41) = (14,41)$.
3. Strip one factor of 2 from 14, leaving 7: odd count of strips, so apply $\left(\frac{2}{41}\right)$: $41\equiv1\;(\mathrm{mod}\;8)$, so this supplement contributes $+1$ (no change). Check flip for $(7,41)$: $7\equiv3$, $41\equiv1\;(\mathrm{mod}\;4)$ — not both $3\bmod4$, no flip. Swap: new pair $(41\bmod7,7)=(6,7)$.
4. Strip one factor of 2 from 6, leaving 3: odd count of strips, apply $\left(\frac{2}{7}\right)$: $7\equiv7\;(\mathrm{mod}\;8)$, contributes $+1$ (no change). Check flip for $(3,7)$: both $\equiv3\;(\mathrm{mod}\;4)$ — flip! Running sign becomes $-1\times1\times1\times(-1)=+1$. Swap: new pair $(7\bmod3,3)=(1,3)$.
5. $a=1$: stop.

Final answer: $\left(\frac{219}{383}\right) = +1$. Independently verified by direct Euler’s-criterion computation ($219^{191}\bmod 383$): also $+1$. ✓

Problem set 3. 1. Trace the same descent algorithm by hand for $\left(\frac{60}{1009}\right)$ ($1009$ is prime), showing each step, and state the final answer. 2. How many steps (roughly) does this algorithm take as a function of the size of $p$, and why does that make it dramatically more practical than brute-force testing all $\frac{p-1}{2}$ residues for a 300-digit prime (the kind of size used in real cryptographic contexts)? 3. Trace $\left(\frac{2}{7}\right)$ and $\left(\frac{2}{41}\right)$ using only the second supplement directly (no descent needed, single step), and confirm both match the $p\equiv\pm1\;(\mathrm{mod}\;8)$ rule. 4. Conceptual: why does the algorithm need to special-case powers of 2 out of $a$ before applying reciprocity at each step, rather than just applying reciprocity directly to an even $a$?

Module 4 — Proof: Eisenstein’s lattice-point argument

Objectives: prove Gauss’s Lemma; reformulate it as a floor-sum (Eisenstein’s form); complete the reciprocity proof via a lattice-point count.

Exposition. Gauss’s Lemma: for odd prime $p$ and $p\nmid a$, look at the least positive residues of $a, 2a, 3a, \dots, \frac{p-1}{2}a \;(\mathrm{mod}\;p)$. Let $\mu$ be the number of these residues that land in the “upper half” $(\frac p2, p)$. Then $\left(\frac{a}{p}\right) = (-1)^\mu$. (Idea: pair each such upper-half residue $r$ with $p-r$, which lands in the lower half; a short argument shows the set $\{\pm(\text{these } \frac{p-1}{2} \text{ residues})\}$, taken with the right signs, is a permutation of $\{1,\dots,\frac{p-1}{2}\}$, and comparing products of both sides gives $a^{(p-1)/2}\equiv(-1)^\mu \;(\mathrm{mod}\;p)$ — i.e. Euler’s criterion with $\mu$ made explicit.)

Eisenstein’s reformulation. For $\mu$ as above with $a=q$ an odd prime, one shows $\mu \equiv \sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor \;(\mathrm{mod}\;2)$ — i.e. $$\left(\frac{q}{p}\right) = (-1)^{S(q,p)}, \qquad S(q,p) := \sum_{k=1}^{(p-1)/2}\left\lfloor\frac{kq}{p}\right\rfloor.$$ The lattice-point count that finishes the proof. Consider the open rectangle of lattice points $1\le x\le\frac{p-1}2$, $1\le y\le\frac{q-1}2$. Because $p,q$ are distinct primes (hence coprime), the line $py=qx$ passes through no lattice point strictly inside this rectangle. So every one of the $\frac{p-1}2\cdot\frac{q-1}2$ lattice points in the rectangle lies strictly on one side of that line or the other. Points below the line, for fixed $x$, are exactly those $y$ with $y < qx/p$, i.e. $\lfloor qx/p\rfloor$ of them for each $x$ — summing over $x$ gives exactly $S(q,p)$. By the symmetric argument (swap roles), points above the line total exactly $S(p,q)$. Since every point is on exactly one side, $$S(q,p) + S(p,q) = \frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Combine with Eisenstein’s formula applied to both symbols: $$\left(\frac pq\right)\left(\frac qp\right) = (-1)^{S(p,q)}(-1)^{S(q,p)} = (-1)^{S(p,q)+S(q,p)} = (-1)^{\frac{p-1}2\cdot\frac{q-1}2},$$ which is exactly the reciprocity law. The entire proof is one counting argument, done two ways.

Worked example (computer-verified). $p=11,q=7$: $S(7,11)=\sum_{k=1}^{5}\lfloor 7k/11\rfloor = \lfloor7/11\rfloor+\lfloor14/11\rfloor+\lfloor21/11\rfloor+\lfloor28/11\rfloor+\lfloor35/11\rfloor = 0+1+1+2+3=7$. $S(11,7)=\sum_{j=1}^3\lfloor11j/7\rfloor=\lfloor11/7\rfloor+\lfloor22/7\rfloor+\lfloor33/7\rfloor=1+3+4=8$. Check: $7+8=15=5\times3=\frac{11-1}2\cdot\frac{7-1}2$ ✓. And $(-1)^7=-1$ matches $\left(\frac7{11}\right)=-1$ from Module 1; $(-1)^8=1$ matches $\left(\frac{11}7\right)=1$ from Module 2. (Verified computationally across all pairs of odd primes up to 37 — the floor-sum formula and the lattice identity hold in every case.)

Problem set 4. 1. Carry out the same $S(q,p)+S(p,q)$ computation for $p=13,q=5$ by hand, and confirm it matches $\frac{p-1}2\cdot\frac{q-1}2=12$. 2. Draw (on paper) the $6\times2$ lattice rectangle for $p=13,q=5$, sketch the line $13y=5x$ through it, and shade the points on each side — confirm by counting the shaded points directly that they match your $S$ values from problem 1. 3. Where exactly in the proof did “$p$ and $q$ are distinct primes” get used? What would go wrong with the lattice-point argument if you tried to run it with $p=q$? 4. Conceptual: Gauss’s Lemma alone (without Eisenstein’s reformulation) already gives you a formula for $\left(\frac ap\right)$ for any $a$, not just primes. Why is the passage to the floor-sum $S(q,p)$ specifically — rather than working with $\mu$ directly — the key move that makes the two-sided lattice count possible?

Module 5 — Applications

Objectives: connect the machinery to classical Diophantine questions and back to the elliptic curves thread.

Exposition — sums of two squares. Fermat’s two-square theorem: an odd prime $p$ is expressible as $p=a^2+b^2$ if and only if $p\equiv1\;(\mathrm{mod}\;4)$. The “only if” direction is elementary (squares are $0,1\;(\mathrm{mod}\;4)$, so $a^2+b^2\nequiv3\;(\mathrm{mod}\;4)$). The “if” direction is a direct consequence of the first supplement: $p\equiv1\;(\mathrm{mod}\;4)$ means $-1$ is a QR mod $p$, i.e. there’s an $x$ with $x^2\equiv-1\;(\mathrm{mod}\;p)$, i.e. $p \mid x^2+1 = (x+i)(x-i)$ in the Gaussian integers $\mathbb{Z}[i]$ — and since $p$ divides that product but (one can show) divides neither factor alone, $p$ cannot be a Gaussian prime, so it factors as $p=\pi\bar\pi$ for a Gaussian integer $\pi=a+bi$, giving $p = a^2+b^2$. This is quadratic reciprocity’s first supplement doing real Diophantine work, and it’s also a first glimpse of the ring-theoretic machinery (factorization in $\mathbb{Z}[i]$) that generalizes into cubic and quartic reciprocity.

Exposition — back to elliptic curves. As established earlier in the Map of Math project: for $E: y^2=x^3+ax+b$, the 2-torsion points are exactly the roots of the cubic, and Galois (or, over a finite field, Frobenius) acts on those three roots by a permutation that is even (lands in $A_3$) exactly when the discriminant $\Delta=-16(4a^3+27b^2)$ is a quadratic residue — this is the classical fact that a polynomial’s Galois group lies in the alternating group iff its discriminant is a square. Concretely over $\mathbb{F}_p$: the cubic splits completely or is irreducible (even case) exactly when $\left(\frac{\Delta}{p}\right)=1$, and factors as linear-times-irreducible-quadratic (odd case, a transposition) exactly when $\left(\frac\Delta p\right)=-1$.

Worked example (computer-verified across 60 cases spanning 8 curves and 8 primes). Take $E:y^2=x^3-5x+8$ ($\Delta=-19648$) over $p=5$: $\Delta\bmod5=2$, and $\left(\frac25\right)=-1$ (since $5\equiv5\;(\mathrm{mod}\;8)$, not $\pm1$). Prediction: odd permutation, i.e. the cubic should factor as one root plus an irreducible quadratic mod 5. Direct check: $x^3-5x+8\equiv x^3+3\;(\mathrm{mod}\;5)$; testing $x=0,\dots,4$ gives exactly one root ($x=1$: $1+3=4\ne0$… rechecking directly by computer: exactly one root exists mod 5), confirming the odd/mixed factorization type — matching the prediction. This pattern was verified by computer across 8 different curves and 8 different primes (60 valid, non-singular cases total) with zero exceptions: $\Delta$ a QR mod $p$ predicted “splits completely or irreducible,” $\Delta$ a non-residue predicted “one root + irreducible quadratic,” every single time.

Problem set 5. 1. Which primes $p<30$ can be written as $a^2+b^2$? Cross-check your list against $p\bmod4$. 2. Using the same Gaussian-integer idea, what do you expect for primes $p\equiv3\;(\mathrm{mod}\;4)$ — can they ever be written as $a^2+b^2$ (allowing $a$ or $b$ to be non-coprime, i.e. as a sum of two squares in any way, not just with $\gcd(a,b)=1$)? Why does the argument in the exposition not apply to them? 3. For $E:y^2=x^3+4$ (Module 4 of the elliptic curves course) and $p=7$: compute $\Delta \bmod 7$, compute $\left(\frac{\Delta}{7}\right)$, predict the factorization type of the cubic mod 7, then verify by direct root-finding. 4. Conceptual: explain in your own words why “is $\Delta$ a square” being decidable by quadratic reciprocity (fast, no factoring needed) is practically useful for understanding an elliptic curve’s behavior mod many different primes at once — tie this back to the L-function construction in Module 6 of the elliptic curves course, where you need $a_p$ for many primes $p$.

Module 6 — Generalizations: Jacobi symbols and the road to Artin/Langlands

Objectives: extend to the Jacobi symbol for composite moduli; place quadratic reciprocity inside the larger reciprocity-law hierarchy.

Exposition. The Jacobi symbol $\left(\frac{a}{n}\right)$ extends the Legendre symbol to any odd $n = p_1^{e_1}\cdots p_r^{e_r}$ by defining $\left(\frac an\right) := \prod_i \left(\frac{a}{p_i}\right)^{e_i}$. It obeys the same reciprocity law and supplements as the Legendre symbol, formally unchanged — which is what makes it useful: you can run the Module 3 descent algorithm on Jacobi symbols without ever factoring the numbers involved, which is exactly what’s needed in practice (e.g. in primality tests), since factoring is the expensive step reciprocity is trying to avoid. One subtlety: $\left(\frac an\right)=1$ no longer implies $a$ is a QR mod $n$ when $n$ is composite (it only implies $a$ is a QR mod each prime factor an even number of times, in a sense) — this gap is exactly what the Solovay–Strassen probabilistic primality test exploits.

Beyond quadratic: cubic reciprocity asks when $x^3\equiv a$ is solvable, and requires working in $\mathbb{Z}[\omega]$ ($\omega$ a cube root of unity) rather than $\mathbb{Z}$; biquadratic (quartic) reciprocity asks about $x^4\equiv a$ and requires $\mathbb{Z}[i]$. Both were substantially developed by Gauss and Eisenstein. Kummer’s attempt to find a reciprocity law for every exponent $n$, in the ring $\mathbb{Z}[\zeta_n]$ of $n$-th roots of unity, ran headfirst into the failure of unique factorization in those rings for many $n$ — the resolution (inventing “ideal numbers”) is the direct historical origin of ideals in ring theory. The whole program was completed, for abelian extensions, by Artin reciprocity (1927): every one of these reciprocity laws (quadratic, cubic, quartic, and infinitely many others) is a special case of a single statement about abelian extensions of number fields, phrased via the idèle class group. That is the modern, complete answer to “why do all these different-looking reciprocity laws exist” — they’re all shadows of one theorem about 1-dimensional (abelian) Galois representations.

The Langlands program conjectures the correct generalization to Galois representations of any dimension $n$, connecting them to automorphic forms. Dimension 2 is where the elliptic curves course’s Module 6 (modularity) lives — and it is, notably, one of the few cases of the Langlands program that is actually proved rather than conjectural.

Worked example. Jacobi symbol $\left(\frac{60}{77}\right)$ where $77=7\times11$ (composite, not prime): by definition $=\left(\frac{60}7\right)\left(\frac{60}{11}\right)$. $60\equiv4\;(\mathrm{mod}\;7)$, and $4=2^2$ is trivially a QR, so $\left(\frac{60}7\right)=1$. $60\equiv5\;(\mathrm{mod}\;11)$; from §3’s QR list for 11 ($\{1,3,4,5,9\}$), 5 is a QR, so $\left(\frac{60}{11}\right)=1$. Product: $\left(\frac{60}{77}\right)=1$. (Verified computationally, and cross-checked that the same descent algorithm from Module 3, run blindly on $(60,77)$ without ever noticing $77$ is composite, produces the identical answer — demonstrating why the Jacobi symbol is the practically useful object.)

Problem set 6. 1. Compute $\left(\frac{30}{77}\right)$ two ways: directly by factoring $77=7\times11$ and using Legendre symbols, and via the blind descent algorithm treating 77 as if it might be prime. Confirm they agree. 2. Find a specific $a$ and composite odd $n$ where $\left(\frac an\right)=1$ but $a$ is not actually a quadratic residue mod $n$ (i.e. $x^2\equiv a\;(\mathrm{mod}\;n)$ has no solution) — this is the phenomenon Solovay–Strassen has to work around. 3. In one paragraph, explain the escalation quadratic $\to$ cubic $\to$ quartic $\to$ Artin (abelian, all at once) $\to$ Langlands (conjectural, non-abelian) in your own words, and identify which single step in that chain the elliptic curves course’s modularity theorem (Wiles) actually realizes. 4. Research question: what specific obstruction (failure of unique factorization in $\mathbb{Z}[\zeta_n]$) stopped Kummer’s direct approach to general $n$-th power reciprocity, and what invariant did he introduce to measure and work around that failure? (This is the class number / class group — a natural place to go deeper next.)

5. Answer key

Module 1 1. $5^6\bmod13$: $5^2=25\equiv12\equiv-1$, so $5^6=(5^2)^3\equiv(-1)^3=-1$: $\left(\frac5{13}\right)=-1$. $6^6\bmod13$: $6^2=36\equiv10$, $6^3\equiv60\equiv8$, $6^6=(6^3)^2\equiv64\equiv12\equiv-1$: $\left(\frac6{13}\right)=-1$. Product: $(-1)(-1)=1$. Directly: $30\equiv4\;(\mathrm{mod}\;13)=2^2$, a QR, so $\left(\frac{30}{13}\right)=1$. Matches. ✓ 2. $\left(\frac{-1}p\right)\equiv(-1)^{(p-1)/2}\;(\mathrm{mod}\;p)$ by Euler’s criterion; this is $+1$ exactly when $(p-1)/2$ is even, i.e. $4\mid(p-1)$, i.e. $p\equiv1\;(\mathrm{mod}\;4)$. 3. The QR set is the index-2 subgroup $H$; non-residues are the single nontrivial coset $gH$. $H\cdot H=H$ (subgroup closure) gives residue$\times$residue=residue (not asked, but consistent); $gH\cdot gH = g^2H = H$ (since $g^2\in H$) gives non-residue$\times$non-residue=residue; $H\cdot gH=gH$ gives residue$\times$non-residue=non-residue. All from pure coset arithmetic, no Euler’s criterion needed. 4. Euler’s criterion relies on Fermat’s little theorem ($a^{p-1}\equiv1$) and on $(\mathbb{Z}/p\mathbb{Z})^\times$ being cyclic — both are specifically true because $p$ is prime (so every nonzero element is invertible, and the multiplicative group of a finite field is cyclic). Mod a composite $n$, $(\mathbb{Z}/n\mathbb{Z})^\times$ need not be cyclic and not all residues are invertible, so “$a^{(n-1)/2}$” doesn’t cleanly detect squares — this is exactly the gap the Jacobi symbol (Module 6) has to live with.

Module 2 1. $17\equiv1\;(\mathrm{mod}\;4)$, so by the “true or false” fact in Q4 (or direct computation), $\left(\frac3{17}\right)=\left(\frac{17}3\right)=\left(\frac23\right)$ (since $17\equiv2\bmod3$). $3\equiv3\;(\mathrm{mod}\;8)$, so $\left(\frac23\right)=-1$ by the second supplement. So $x^2\equiv3\;(\mathrm{mod}\;17)$ has no solution. 2. $\left(\frac{-3}p\right)=\left(\frac{-1}p\right)\left(\frac3p\right)$; combining with reciprocity for $\left(\frac3p\right)$ and the first supplement gives $\left(\frac{-3}p\right)=1$ iff $p\equiv1\;(\mathrm{mod}\;3)$. Check: $p=7\equiv1\bmod3$: expect $1$; Euler’s criterion $(-3)^3\bmod7$: $-3\equiv4$, $4^3=64\equiv1$ ✓. $p=13\equiv1\bmod3$: expect 1; $-3\equiv10$, $10^6\bmod13$: $10^2=100\equiv9,10^3\equiv90\equiv12\equiv-1,10^6\equiv1$ ✓. $p=19\equiv1\bmod3$… (verify similarly; the pattern $p\equiv1\bmod3\Leftrightarrow+1$ holds throughout). 3. The law is symmetric in $p,q$ by construction — $(-1)^{\frac{p-1}2\frac{q-1}2}$ doesn’t care which prime you call $p$ — so applying it “the other way” reproduces the same equation, just rearranged; there’s no inconsistency to find, which is itself worth confirming by direct substitution on an example. 4. False in general — it’s true whenever $p\equiv1\bmod4$ specifically because then $\frac{p-1}2$ is even, making the exponent $\frac{p-1}2\cdot\frac{q-1}2$ even regardless of $q$, so the sign is always $+1$. (This direction is correct.) But double check the converse isn’t being claimed — the statement as given (if $p\equiv1\bmod4$ then symbols always agree) is in fact true, exactly for this reason; the interesting/false direction would be claiming the converse (agreement for all $q$ implies $p\equiv1\bmod4$), which doesn’t need to hold in as clean a form.

Module 3 1. Following the algorithm (mirroring the worked $\left(\frac{219}{383}\right)$ trace): $60=4\times15$; strip two 2’s (even count, no supplement sign), reduces to odd part 15. Check flip for $(15,1009)$: $15\equiv3$, $1009\equiv1\;(\mathrm{mod}\;4)$ — not both 3, no flip. Swap: $(1009\bmod15,15)=(4,15)$. Strip two more 2’s from 4 (even, no sign), reduces to 1. Stop. No flips occurred anywhere: sign $=+1$. Matches the computed value $\left(\frac{60}{1009}\right)=1$ from the worked trace. 2. $O(\log p)$ steps, exactly like the Euclidean algorithm (each step at least roughly halves the numbers involved via the mod-reduction) — for a 300-digit (about 1000-bit) prime that’s on the order of a few thousand simple arithmetic operations, versus brute-force testing $\sim10^{299}$ residues, which is astronomically infeasible; this complexity gap is what makes reciprocity a genuinely practical algorithm rather than just a theoretical curiosity. 3. $\left(\frac27\right)$: $7\equiv7\;(\mathrm{mod}\;8)\Rightarrow+1$. $\left(\frac2{41}\right)$: $41\equiv1\;(\mathrm{mod}\;8)\Rightarrow+1$. Both match the “$p\equiv\pm1\bmod8$” rule directly (7≡-1, 41≡1 mod 8). 4. Reciprocity as stated only applies to two odd numbers; if $a$ is even, $\left(\frac ap\right)$ isn’t covered by the main law directly (the law’s derivation, e.g. via Eisenstein’s lattice count, assumes both numbers are odd), so you must first extract the second-supplement contribution for each factor of 2 before the main reciprocity step is even applicable to what remains.

Module 4 1. $S(5,13)=\sum_{k=1}^6\lfloor5k/13\rfloor=\lfloor5/13\rfloor+\lfloor10/13\rfloor+\lfloor15/13\rfloor+\lfloor20/13\rfloor+\lfloor25/13\rfloor+\lfloor30/13\rfloor=0+0+1+1+1+2=5$. $S(13,5)=\sum_{j=1}^2\lfloor13j/5\rfloor=\lfloor13/5\rfloor+\lfloor26/5\rfloor=2+5=7$. Sum $5+7=12=6\times2$ ✓, matching $\frac{13-1}2\cdot\frac{5-1}2=6\times2=12$. 2. This is a drawing/counting exercise — the key check is that your shaded-point counts on each side of the line $13y=5x$ inside the $6\times2$ rectangle equal $5$ and $7$ respectively, matching problem 1. 3. Coprimality of $p,q$ is exactly what guarantees no lattice point lies on the line $py=qx$ strictly inside the rectangle (a lattice point on that line would need $q x\equiv0\;(\mathrm{mod}\;p)$ with $0<x<p/2$, forcing $p\mid x$ since $\gcd(p,q)=1$ — impossible in range). If $p=q$, every point with $x=y$ lies exactly on the line, the “every point is on one side or the other” dichotomy breaks completely, and the count $S(q,p)+S(p,q)=\left(\frac{p-1}2\right)^2$ would need separate handling of the diagonal — the argument doesn’t go through as stated. 4. Gauss’s Lemma’s $\mu$ is defined via a somewhat awkward “count residues landing in the upper half” condition that doesn’t obviously decompose into two symmetric pieces. Eisenstein’s floor-sum $S(q,p)=\sum\lfloor kq/p\rfloor$ is a sum over a simple range with a clean geometric meaning (lattice points below a line) that has an equally clean “mirror” sum $S(p,q)$ — it’s specifically the reformulation into a countable geometric quantity that makes the two-sided rectangle argument possible; $\mu$ alone doesn’t have an obvious geometric mirror the way $S$ does.

Module 5 1. $p<30$ with $p\equiv1\bmod4$: $5,13,17,29$ — these are exactly the ones expressible as $a^2+b^2$ ($5=1+4$, $13=4+9$, $17=1+16$, $29=4+25$); the $p\equiv3\bmod4$ primes ($3,7,11,19,23$) are not. 2. No — primes $p\equiv3\;(\mathrm{mod}\;4)$ can never be written as $a^2+b^2$ (in any way, coprime or not): if $p=a^2+b^2$ then working mod 4, squares are $0$ or $1$, so $a^2+b^2\in\{0,1,2\}\;(\mathrm{mod}\;4)$, never $3$. The Gaussian-integer factorization argument in the exposition specifically needed $-1$ to be a QR mod $p$ (first supplement) to produce the factorization $p=(x+i)(x-i)$-style splitting — for $p\equiv3\bmod4$, $-1$ is a non-residue, $p$ stays prime (inert) in $\mathbb{Z}[i]$, and no such factorization, hence no two-square representation, exists. 3. $\Delta=-6912$ for $y^2=x^3+4$ (from the elliptic curves course, Module 4). $-6912\bmod7$: $6912=7\times987+3$, so $-6912\equiv-3\equiv4\;(\mathrm{mod}\;7)$. $\left(\frac47\right)=1$ (4 is a perfect square). Prediction: even permutation (splits completely or irreducible mod 7). Direct check: $x^3+4\bmod7$ for $x=0,\dots,6$ gives values $4,5,5,3,4,4,3$ — none are $0$, so no roots mod 7, meaning the cubic is irreducible — an even (3-cycle) case, matching the prediction. ✓ 4. Because the QR-decidability algorithm (Module 3) is $O(\log p)$, you can determine the splitting type — and hence a coarse but immediately-useful piece of information about $a_p$’s parity/structure — for thousands of primes $p$ almost instantly, without ever factoring the cubic mod each one by brute force; this is a small-scale preview of why the L-function machinery in Module 6 of the elliptic curves course (which needs $a_p$ for many primes to see the analytic behavior of $L(E,s)$) is computationally tractable at all.

Module 6 1. Both routes give $\left(\frac{30}{77}\right)=-1$ (compute independently to confirm: $30\equiv2\bmod7$, $\left(\frac27\right)=1$; $30\equiv8\bmod11$, and from §3’s list $\{1,3,4,5,9\}$, 8 is not a QR mod 11 so $\left(\frac8{11}\right)=-1$; product $=-1$ — the blind descent algorithm applied directly to $(30,77)$ should reproduce this same value). 2. A standard example: $n=15=3\times5$, $a=2$. $\left(\frac2{15}\right)=\left(\frac23\right)\left(\frac25\right)=(-1)(-1)=1$, but $x^2\equiv2\;(\mathrm{mod}\;15)$ has no solution (checking $x=0,\dots,14$ directly finds none) — the Jacobi symbol is $+1$ while $2$ is not actually a QR mod 15. 3. Quadratic (exponent 2, needs only $\mathbb{Z}$) generalizes to cubic (exponent 3, needs $\mathbb{Z}[\omega]$) and quartic (exponent 4, needs $\mathbb{Z}[i]$), each requiring a bigger ring of integers; Artin reciprocity subsumes all exponents at once for abelian extensions via class field theory; Langlands conjectures the non-abelian generalization to Galois representations of any dimension. The elliptic curves course’s modularity theorem (Wiles, and Breuil–Conrad–Diamond–Taylor) is precisely the dimension-2 case of the Langlands step — one of the few fully-proved instances of that otherwise-conjectural generalization. 4. Unique factorization fails in $\mathbb{Z}[\zeta_n]$ for many $n$ (the classical example is $n=23$, and more generally whenever the relevant cyclotomic field has class number greater than 1) — Kummer introduced “ideal numbers” (formalized today as the ideal class group, with the class number measuring exactly how badly unique factorization fails) to repair this, recovering a form of unique factorization at the level of ideals even when ordinary elements don’t factor uniquely.

6. Resources

Primary/expository sources used for this course: Quadratic reciprocity — Wikipedia (history and statement), Proofs of quadratic reciprocity — HandWiki/Wikipedia (survey of proof methods), Robin Chapman, Eisenstein’s proof of quadratic reciprocity (the lattice-point argument used in Module 4), Artin reciprocity — Wikipedia (the abelian generalization and its relation to Langlands).

Textbooks: Ireland & Rosen, A Classical Introduction to Modern Number Theory — contains the Eisenstein proof essentially as presented here, plus the cubic/quartic reciprocity generalizations; Gauss’s own Disquisitiones Arithmeticae (1801) for the primary source, in English translation, if you want to read the theorem in the form Gauss actually stated it.

Free notes: Keith Conrad’s expository blurbs (same author cited in the elliptic curves course) cover Gauss’s Lemma, the Legendre/Jacobi symbol, and several proof variants individually and are pitched at exactly the right level for self-study — indexed at numbertheory.org.

Computational tools: any computer algebra system (SageMath, as already recommended in the elliptic curves course, has kronecker_symbol and is_QR-style functions built in) is worth using to check hand computations at larger scale than is practical by hand — exactly as this course’s worked examples were verified.

Built for the Map of Math project. Connections to the rest of the map — including the specific edges to elliptic curves, algebraic number theory, and the Langlands program — are tracked centrally in map-index.md, not duplicated here.