Jacobi Symbol and Generalized Reciprocity

⚡ Key Takeaways

The Jacobi symbol $\left(\frac{a}{n}\right)$ generalizes the Legendre symbol to all odd positive moduli $n$ by multiplicativity over the prime factorization of $n$ , satisfying a clean reciprocity law $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}$ . It is a fully multiplicative, computable function that does not detect quadratic residuosity for composite $n$ , yet it enables fast evaluation of Legendre symbols and underpins primality testing, cryptography, and the modern theory of power reciprocity. Introduced by Carl Gustav Jacob Jacobi in 1837.

💡 The Core Insight

The Jacobi symbol is the unique completely multiplicative extension (in the numerator) and multiplicative extension (in the denominator) of the Legendre symbol that preserves the reciprocity law. By trading the arithmetic meaning ("is $a$ a square mod $n$ ?") for algebraic multiplicativity, one obtains a function that satisfies an unconditional, factorization-free reciprocity, turning symbol evaluation into a Euclidean-style descent analogous to computing a $\gcd$ .

DefinitionLegendre Symbol

For an odd prime $p$ and integer $a$ , the Legendre symbol is

1

\quad \left(\frac{a}{p}\right)=\begin{cases}0 & p\mid a,\\ +1 & a \text{ is a nonzero quadratic residue mod } p,\\ -1 & a \text{ is a quadratic non-residue mod } p.\end{cases}

Derivation hint: The nonzero residues mod $p$ form a cyclic group of order $p-1$ ; squares are the unique index-2 subgroup, so exactly half are residues, giving the $\pm1$ split. By Euler's criterion,

2

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

Derivation hint: In the cyclic group $(\mathbb{Z}/p)^\times$ , $a^{(p-1)/2}=\pm1$ ; it equals $+1$ iff $a$ lies in the index-2 subgroup of squares, by Lagrange and the order of a generator.

DefinitionJacobi Symbol

Let $n>0$ be odd with prime factorization $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ . For any integer $a$ , the Jacobi symbol is

3

\quad \left(\frac{a}{n}\right)=\prod_{i=1}^{k}\left(\frac{a}{p_i}\right)^{e_i},

with the conventions $\left(\frac{a}{1}\right)=1$ for all $a$ , and $\left(\frac{a}{n}\right)=0$ whenever $\gcd(a,n)>1$ . Derivation hint: This is a definition, but it is forced by requiring multiplicativity in the denominator: $\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$ , anchored at primes by the Legendre symbol. Here every symbol $\left(\frac{a}{p_i}\right)$ on the right is a Legendre symbol; $a$ is the numerator, $n$ the denominator. The value lies in $\{-1,0,+1\}$ .

TheoremFundamental Properties

For odd positive $n,m$ and integers $a,b$ : 1. Completely multiplicative in the top: $\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$ . 2. Multiplicative in the bottom: $\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$ . 3. Periodicity: $a\equiv b \pmod n \implies \left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$ . 4. Quadratic Reciprocity:

4

\quad \left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}\qquad(\gcd(m,n)=1,\ m,n\text{ odd}>0).

Derivation hint: Multiply the prime-level Legendre reciprocity over all prime factors of $m$ and $n$ ; the sign-exponent collapses because $\frac{m-1}{2}\equiv\sum_i \frac{p_i-1}{2}\pmod 2$ for odd $m=\prod p_i$ (Lemma below). 5. First Supplement:

5

\quad \left(\frac{-1}{n}\right)=(-1)^{(n-1)/2}=\begin{cases}+1 & n\equiv 1\pmod 4,\\ -1 & n\equiv 3\pmod 4.\end{cases}

Derivation hint: $\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}$ at primes; multiply over factors and use $\frac{n-1}{2}\equiv\sum\frac{p_i-1}{2}$ mod 2. 6. Second Supplement:

6

\quad \left(\frac{2}{n}\right)=(-1)^{(n^2-1)/8}=\begin{cases}+1 & n\equiv \pm1\pmod 8,\\ -1 & n\equiv \pm3\pmod 8.\end{cases}

Derivation hint: $\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$ at primes; multiply over factors using $\frac{n^2-1}{8}\equiv\sum\frac{p_i^2-1}{8}\pmod 2$ for odd $n$ .

ProofReciprocity from the Sign Lemma

We reduce the Jacobi law to the Legendre law via two congruence lemmas.

Step 1 — Sign Lemma (additivity mod 2). For odd integers $r,s$ ,

7

\quad \frac{rs-1}{2}\equiv \frac{r-1}{2}+\frac{s-1}{2}\pmod 2,\qquad \frac{r^2s^2-1}{8}\equiv\frac{r^2-1}{8}+\frac{s^2-1}{8}\pmod 2.

Derivation hint: Write $r=1+2x$ , $s=1+2y$ ; then $\frac{rs-1}{2}-\frac{r-1}{2}-\frac{s-1}{2}=2xy\equiv0\pmod2$ . The second follows similarly from $r^2-1=(r-1)(r+1)$ being divisible by $8$ for odd $r$ . By induction, for $n=\prod_i p_i$ (with multiplicity), $\frac{n-1}{2}\equiv\sum_i\frac{p_i-1}{2}$ and $\frac{n^2-1}{8}\equiv\sum_i\frac{p_i^2-1}{8}\pmod 2$ .

Step 2 — Supplements. Using $\left(\frac{-1}{p_i}\right)=(-1)^{(p_i-1)/2}$ ,

\left(\frac{-1}{n}\right)=\prod_i(-1)^{e_i\frac{p_i-1}{2}}=(-1)^{\sum_i e_i\frac{p_i-1}{2}}=(-1)^{(n-1)/2},

by Step 1. The identical argument with $\left(\frac{2}{p_i}\right)$ yields equation [6].

Step 3 — Main reciprocity. Write $m=\prod_i p_i$ , $n=\prod_j q_j$ (with multiplicity). By full multiplicativity in both arguments,

\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=\prod_{i,j}\left(\frac{p_i}{q_j}\right)\left(\frac{q_j}{p_i}\right)=\prod_{i,j}(-1)^{\frac{p_i-1}{2}\frac{q_j-1}{2}},

using the Legendre reciprocity at each prime pair $(p_i,q_j)$ . The exponent is

\sum_{i,j}\frac{p_i-1}{2}\frac{q_j-1}{2}=\Big(\sum_i\frac{p_i-1}{2}\Big)\Big(\sum_j\frac{q_j-1}{2}\Big)\equiv\frac{m-1}{2}\cdot\frac{n-1}{2}\pmod 2,

by Step 1. This proves [4]. $\blacksquare$

∎

⚠️ Common mistake

The proof assumes the Legendre-level reciprocity for primes. The Jacobi reciprocity is therefore not a new theorem about residues — it is a bookkeeping extension. Its power is computational, not informational: it lets you reduce a symbol while the moduli factor "invisibly."

mathematician · Carl Gustav Jacob Jacobi | 1804–1851

Jacobi, a foundational figure of 19th-century analysis and number theory, introduced the symbol bearing his name in 1837 while studying cubic and higher reciprocity and the theory of elliptic functions. His motivation was algorithmic and structural: he sought to formulate reciprocity in a way that survived passage to composite moduli, freeing computations from the need to factor. The symbol became the prototype for the Kronecker symbol (extending to all integers, including even and negative denominators) and the local Hilbert symbol, and ultimately for Artin reciprocity in class field theory. Jacobi held chairs at Königsberg and Berlin and revolutionized the calculus of variations, dynamics (Hamilton–Jacobi theory), and determinants (the Jacobian).

🧠 Intuition

Think of the Legendre symbol as a character — a homomorphism $\chi_p:(\mathbb{Z}/p)^\times\to\{\pm1\}$ detecting squareness. The Jacobi symbol $\left(\frac{\cdot}{n}\right)$ is again a real character mod $n$ (when restricted to $a$ coprime to $n$ ), but it detects squareness in the group $(\mathbb{Z}/n)^\times$ only partially. The group of squares in $(\mathbb{Z}/n)^\times$ has index $2^k$ (for $k$ distinct odd prime factors), but the Jacobi character has only two values $\pm1$ — so it sees a single $\mathbb{Z}/2$ quotient of a $(\mathbb{Z}/2)^k$ "obstruction group." A Jacobi value of $+1$ means "an even number of the local symbols are $-1$ ," which is far weaker than "all local symbols are $+1$ ." Reciprocity, meanwhile, behaves like a Euclidean algorithm with signs: flipping $\left(\frac{m}{n}\right)\to\left(\frac{n}{m}\right)$ and reducing $n \bmod m$ shrinks the arguments just like $\gcd$ , with the $(-1)$ factors tracking parity of $\frac{m-1}{2}\frac{n-1}{2}$ .

Figure

Euclidean-style descent for evaluating a Jacobi symbol; the highlighted path shows reduction, factoring out 2's, and reciprocity flips.

```svg

```

ExampleEvaluating a Jacobi symbol by reciprocity

Given: Compute $\left(\frac{1001}{9907}\right)$ . Note $9907$ is prime (so this is also a Legendre symbol), but we evaluate it using only Jacobi reciprocity, never testing residuosity.

Steps:

Both odd, $\gcd(1001,9907)=1$ . Apply [4]: $1001\equiv1\pmod4$ , so the sign is $+1$ .

\left(\frac{1001}{9907}\right)=\left(\frac{9907}{1001}\right).

Reduce: $9907 = 9\cdot1001 + 898$ , so $\left(\frac{9907}{1001}\right)=\left(\frac{898}{1001}\right)$ .
Factor 2: $898=2\cdot449$ , so $=\left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right)$ . Since $1001\equiv1\pmod8$ , $\left(\frac{2}{1001}\right)=+1$ .
Flip $\left(\frac{449}{1001}\right)$ : $449\equiv1\pmod4$ , sign $+1$ , $=\left(\frac{1001}{449}\right)$ . Reduce $1001=2\cdot449+103$ , $=\left(\frac{103}{449}\right)$ .
Flip: $103\equiv3,\ 449\equiv1\pmod4$ , sign $+1$ , $=\left(\frac{449}{103}\right)$ . Reduce $449=4\cdot103+37$ , $=\left(\frac{37}{103}\right)$ .
Flip: $37\equiv1\pmod4$ , $=\left(\frac{103}{37}\right)$ . Reduce $103=2\cdot37+29$ , $=\left(\frac{29}{37}\right)$ .
Flip: $29\equiv1\pmod4$ , $=\left(\frac{37}{29}\right)=\left(\frac{8}{29}\right)=\left(\frac{2}{29}\right)^3$ . Since $29\equiv5\pmod8$ , $\left(\frac{2}{29}\right)=-1$ , so $(-1)^3=-1$ .

Answer:

\boxed{\left(\frac{1001}{9907}\right)=-1.}

(No factorization of $1001=7\cdot11\cdot13$ was ever required.)

ExampleThe symbol fails to detect a residue

Given: Let $n=15=3\cdot5$ and $a=2$ . Determine $\left(\frac{2}{15}\right)$ and compare with whether $2$ is actually a quadratic residue mod $15$ .

Steps:

By [3]: $\left(\frac{2}{15}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)$ .
$\left(\frac{2}{3}\right)$ : $3\equiv3\pmod8\Rightarrow-1$ . $\left(\frac{2}{5}\right)$ : $5\equiv5\pmod8\Rightarrow-1$ .
Product: $(-1)(-1)=+1$ .
Check residuosity: the squares mod 15 are $\{1,4,9,6,10\}$ ( $1^2,2^2,3^2,4^2,5^2,\dots$ ). $2$ is not among them. So $2$ is a quadratic non-residue mod 15, yet the Jacobi symbol is $+1$ .

Answer:

\boxed{\left(\frac{2}{15}\right)=+1\ \text{but}\ 2\ \text{is a non-residue mod }15.}

This is the defining limitation of the Jacobi symbol.

⚠️ Common mistake

The Jacobi symbol does NOT test quadratic residuosity for composite $n$ . $\left(\frac{a}{n}\right)=-1$ does guarantee $a$ is a non-residue (since at least one local Legendre factor is $-1$ ). But $\left(\frac{a}{n}\right)=+1$ guarantees nothing: it only says an even number of local factors are $-1$ . True residuosity mod $n$ requires $\left(\frac{a}{p}\right)=+1$ for every prime $p\mid n$ , which the single value $\pm1$ cannot encode.

⚠️ Common mistake

Denominator must be odd and positive in the classical Jacobi symbol. Expressions like $\left(\frac{3}{4}\right)$ or $\left(\frac{5}{-7}\right)$ are undefined as Jacobi symbols. To handle even or negative bottoms, switch to the Kronecker Symbol, which sets $\left(\frac{a}{2}\right)=(-1)^{(a^2-1)/8}$ and $\left(\frac{a}{-1}\right)=\operatorname{sgn}(a)$ .

Counterexample

Consider $a=2$ , $n=9907$ (prime) versus $n=21=3\cdot7$ . We have $\left(\frac{2}{9907}\right)=\left(\frac{2}{21}\right)$ may both equal $+1$ , yet they "mean" different things: for the prime modulus it correctly signals a residue, while for $21$ , $\left(\frac{2}{21}\right)=\left(\frac{2}{3}\right)\left(\frac{2}{7}\right)=(-1)(+1)=-1$ — actually $-1$ , confirming a non-residue. A subtler counterexample: $\left(\frac{4}{15}\right)=\left(\frac{2}{15}\right)^2=+1$ and indeed $4$ is a residue, while $\left(\frac{2}{15}\right)=+1$ with $2$ a non-residue. The symbol cannot distinguish these cases, demonstrating that " $+1$ " is genuinely ambiguous.

connection

The Jacobi symbol sits in a tower of generalizations. Below it is the Legendre Symbol, its prime-modulus special case. Above it, the Kronecker Symbol extends the denominator to all of $\mathbb{Z}$ and packages Jacobi symbols into the theory of real Dirichlet characters $\chi_d(\cdot)=\left(\frac{d}{\cdot}\right)$ , central to Dirichlet L-functions and the class number formula. In algebraic number theory, the right framework is the power residue symbol and the local Hilbert Symbol, whose product formula $\prod_v (a,b)_v=1$ is equivalent to quadratic reciprocity; this is the gateway to Artin Reciprocity and class field theory. The Euclidean descent of reciprocity is structurally parallel to the Euclidean Algorithm, and the supplements [5]–[6] are the splitting laws for $-1$ and $2$ in Quadratic Number Fields.

🔬 Where this appears

⏳ History

- 1640s–1650s — Fermat: Studies of representations

p=x^2+y^2

and the "little theorem" lay groundwork for residue theory.

- 1772–1783 — Euler: Discovers the law of quadratic reciprocity empirically and proves Euler's criterion (equation [2]), the bridge between residuosity and exponentiation.

- 1785 — Legendre: Introduces the Legendre symbol and states reciprocity (with gaps in proof); coins the multiplicative

\pm1

notation.

- 1796–1801 — Gauss: Gives the first complete proof (the theorema aureum) in Disquisitiones Arithmeticae (1801), ultimately producing eight distinct proofs over his lifetime.

- 1837 — Jacobi: Defines the Jacobi symbol and proves that reciprocity and its supplements extend to odd composite moduli, enabling factorization-free computation.

- 1846–1850s — Eisenstein, Kummer: Extend reciprocity to cubic, biquadratic, and higher powers; Kummer's ideal numbers and power residue symbols generalize Jacobi's idea.

- 1880s — Kronecker: Introduces the Kronecker symbol, extending the denominator to all integers and linking to Dirichlet characters and class numbers.

- 1920s — Hilbert, Artin: Hilbert's symbol and Artin reciprocity recast all reciprocity laws as statements in class field theory; quadratic reciprocity becomes the product formula for local symbols.

- 1977 — Solovay & Strassen: Apply Jacobi symbols to randomized primality testing, igniting computational number theory and modern cryptography.

open-problem

The quadratic residuosity problem (QRP) — given $n=pq$ and $a$ with $\left(\frac{a}{n}\right)=+1$ , decide whether $a$ is a true residue mod $n$ — is widely believed intractable without factoring $n$ , but this is unproven; it is not known to be NP-hard, nor reducible from factoring in the worst case. A polynomial QRP algorithm would break the Goldwasser–Micali and Cocks schemes. More broadly, the higher-power reciprocity laws have explicit but combinatorially intricate symbols (Hilbert, Artin), and effective, fully explicit reciprocity for general number fields — controlling constants and the size of the "conductor" — remains an active area. On the analytic side, the distribution of Jacobi symbol values relates to least-quadratic-nonresidue bounds, where the gap between conditional (GRH) bounds $O(\log^2 p)$ and unconditional ones $O(p^{1/4+\epsilon})$ (Burgess) is a long-standing open question.

Jacobi Symbol and Generalized Reciprocity

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also