Jacobi Symbol and Generalized Reciprocity

The Jacobi symbol $(\frac{a}{n})$ generalizes the Legendre symbol to all odd positive moduli $n$ by multiplicativity over the prime factorization of $n$ , satisfying a clean reciprocity law $(\frac{m}{n}) (\frac{n}{m}) = (- 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 Jacobi symbol extends the Legendre symbol from prime moduli to arbitrary odd positive moduli. For odd $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ and integer $a$ , it is defined as the product $\prod_{i} (\frac{a}{p _{i}})^{e_{i}}$ of Legendre symbols. Its central virtue is that the quadratic reciprocity law and its supplements persist verbatim at this level of generality, which makes the symbol computable in $O (lo g^{2} n)$ bit operations without factoring $n$ . The surprising and crucial fact is a loss of information: $(\frac{a}{n}) = + 1$ does not imply that $a$ is a quadratic residue mod $n$ — the Jacobi symbol can be $+ 1$ even when $a$ is a non-residue. This gap between the symbol and genuine residuosity is precisely what the Solovay–Strassen primality test and several cryptosystems exploit.

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 $g cd$ .

Formal Statement

Legendre Symbol

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

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0 + 1 - 1 p ∣ a, a is a nonzero quadratic residue mod p, a is a quadratic non-residue mod p .

⟳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

\pm 1

split.

By Euler's criterion,

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p) .

⟳In the cyclic group

(Z / p)^{\times}

a^{(p - 1) /2} = \pm 1

; it equals

+ 1

iff

a

lies in the index-2 subgroup of squares, by Lagrange and the order of a generator.

Jacobi Symbol

Let $n > 0$ be odd with prime factorization $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ . For any integer $a$ , the Jacobi symbol is

(\frac{a}{n}) = i = 1 \prod k (\frac{a}{p _{i}})^{e_{i}},

with the conventions $(\frac{a}{1}) = 1$ for all $a$ , and $(\frac{a}{n}) = 0$ whenever $g cd (a, n) > 1$ .

⟳This is a definition, but it is forced by requiring multiplicativity in the denominator:

(\frac{a}{mn}) = (\frac{a}{m}) (\frac{a}{n})

, anchored at primes by the Legendre symbol.

Here every symbol $(\frac{a}{p _{i}})$ on the right is a Legendre symbol; $a$ is the numerator, $n$ the denominator. The value lies in ${- 1, 0, + 1}$ .

Fundamental Properties

For odd positive $n, m$ and integers $a, b$ :

Completely multiplicative in the top: $(\frac{ab}{n}) = (\frac{a}{n}) (\frac{b}{n})$ .
Multiplicative in the bottom: $(\frac{a}{mn}) = (\frac{a}{m}) (\frac{a}{n})$ .
Periodicity: $a \equiv b (mod n) ⟹ (\frac{a}{n}) = (\frac{b}{n})$ .
Quadratic Reciprocity:

(\frac{m}{n}) (\frac{n}{m}) = (- 1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}} (g cd (m, n) = 1, m, n odd > 0) .

⟳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} (mod 2)

for odd

m = \prod p_{i}

(Lemma below).

First Supplement:

(\frac{- 1}{n}) = (- 1)^{(n - 1) /2} = {+ 1 - 1 n \equiv 1 (mod 4), n \equiv 3 (mod 4) .

⟳

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2}

at primes; multiply over factors and use

\frac{n - 1}{2} \equiv \sum \frac{p _{i} - 1}{2}

mod 2.

Second Supplement:

(\frac{2}{n}) = (- 1)^{(n^{2} - 1) /8} = {+ 1 - 1 n \equiv \pm 1 (mod 8), n \equiv \pm 3 (mod 8) .

⟳

(\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8}

at primes; multiply over factors using

\frac{n ^{2} - 1}{8} \equiv \sum \frac{p _{i}^{2} - 1}{8} (mod 2)

for odd

n

Why It Holds / Derivation

Reciprocity 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

\frac{r s - 1}{2} \equiv \frac{r - 1}{2} + \frac{s - 1}{2} (mod 2), \frac{r ^{2} s ^{2} - 1}{8} \equiv \frac{r ^{2} - 1}{8} + \frac{s ^{2} - 1}{8} (mod 2) .

⟳Write

r = 1 + 2 x

s = 1 + 2 y

; then

\frac{r s - 1}{2} - \frac{r - 1}{2} - \frac{s - 1}{2} = 2 x y \equiv 0 (mod 2)

. 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} (mod 2)$ .

Step 2 — Supplements. Using

(\frac{- 1}{p _{i}}) = (- 1)^{(p_{i} - 1) /2}

(\frac{- 1}{n}) = i \prod (- 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

(\frac{2}{p _{i}})

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,

(\frac{m}{n}) (\frac{n}{m}) = i, j \prod (\frac{p _{i}}{q _{j}}) (\frac{q _{j}}{p _{i}}) = i, j \prod (- 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

i, j \sum \frac{p _{i} - 1}{2} \frac{q _{j} - 1}{2} = (i \sum \frac{p _{i} - 1}{2}) (j \sum \frac{q _{j} - 1}{2}) \equiv \frac{m - 1}{2} \cdot \frac{n - 1}{2} (mod 2),

by Step 1. This proves [4].

■

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."

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).

Building Intuition

Think of the Legendre symbol as a character — a homomorphism $χ_{p} : (Z / p)^{\times} \to {\pm 1}$ detecting squareness. The Jacobi symbol $(\frac{\cdot}{n})$ is again a real character mod $n$ (when restricted to $a$ coprime to $n$ ), but it detects squareness in the group $(Z / n)^{\times}$ only partially. The group of squares in $(Z / n)^{\times}$ has index $2^{k}$ (for $k$ distinct odd prime factors), but the Jacobi character has only two values $\pm 1$ — so it sees a single $Z /2$ quotient of a $(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 $(\frac{m}{n}) \to (\frac{n}{m})$ and reducing $n mod m$ shrinks the arguments just like $g cd$ , with the $(- 1)$ factors tracking parity of $\frac{m - 1}{2} \frac{n - 1}{2}$ .

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

<svg viewBox="0 0 640 360" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="360" fill="#0a0e17"/>
<text x="20" y="30" fill="#e2e8f0" font-size="16" font-family="monospace">Compute (1001 / 9907)</text>
<line x1="40" y1="50" x2="600" y2="50" stroke="#94a3b8" stroke-width="1"/>
<text x="40" y="80" fill="#e2e8f0" font-size="14" font-family="monospace">reciprocity flip  →  (9907/1001) · (−1)^( (1000/2)(9906/2) )</text>
<text x="40" y="110" fill="#e2e8f0" font-size="14" font-family="monospace">reduce  9907 mod 1001 = 894  →  (894/1001)</text>
<text x="40" y="140" fill="#e2e8f0" font-size="14" font-family="monospace">factor 2:  894 = 2·447  →  (2/1001)(447/1001)</text>
<text x="40" y="170" fill="#e2e8f0" font-size="14" font-family="monospace">(2/1001): 1001≡1 mod 8  →  +1</text>
<text x="40" y="200" fill="#e2e8f0" font-size="14" font-family="monospace">flip (447/1001) → (1001/447), reduce 1001 mod 447 = 107</text>
<text x="40" y="230" fill="#e2e8f0" font-size="14" font-family="monospace">… continue Euclidean descent …</text>
<path d="M40 250 Q200 250 320 280 T600 300" stroke="#d4a853" stroke-width="2.5" fill="none"/>
<text x="40" y="330" fill="#d4a853" font-size="15" font-family="monospace">descent terminates at (a/1)=1  ⇒  final value ±1</text>
<circle cx="600" cy="300" r="5" fill="#d4a853"/>
<text x="500" y="270" fill="#94a3b8" font-size="12" font-family="monospace">arguments shrink</text>
</svg>

Worked Examples

Evaluating a Jacobi symbol by reciprocity

Given: Compute

(\frac{1001}{9907})

. 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, $g cd (1001, 9907) = 1$ . Apply [4]: $1001 \equiv 1 (mod 4)$ , so the sign is $+ 1$ .

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

Reduce: $9907 = 9 \cdot 1001 + 898$ , so $(\frac{9907}{1001}) = (\frac{898}{1001})$ .
Factor 2: $898 = 2 \cdot 449$ , so $= (\frac{2}{1001}) (\frac{449}{1001})$ . Since $1001 \equiv 1 (mod 8)$ , $(\frac{2}{1001}) = + 1$ .
Flip $(\frac{449}{1001})$ : $449 \equiv 1 (mod 4)$ , sign $+ 1$ , $= (\frac{1001}{449})$ . Reduce $1001 = 2 \cdot 449 + 103$ , $= (\frac{103}{449})$ .
Flip: $103 \equiv 3, 449 \equiv 1 (mod 4)$ , sign $+ 1$ , $= (\frac{449}{103})$ . Reduce $449 = 4 \cdot 103 + 37$ , $= (\frac{37}{103})$ .
Flip: $37 \equiv 1 (mod 4)$ , $= (\frac{103}{37})$ . Reduce $103 = 2 \cdot 37 + 29$ , $= (\frac{29}{37})$ .
Flip: $29 \equiv 1 (mod 4)$ , $= (\frac{37}{29}) = (\frac{8}{29}) = (\frac{2}{29})^{3}$ . Since $29 \equiv 5 (mod 8)$ , $(\frac{2}{29}) = - 1$ , so $(- 1)^{3} = - 1$ .

Answer:

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

(No factorization of

1001 = 7 \cdot 11 \cdot 13

was ever required.)

The symbol fails to detect a residue

Given: Let

n = 15 = 3 \cdot 5

and

a = 2

. Determine

(\frac{2}{15})

and compare with whether

2

is actually a quadratic residue mod

15

. Steps:

By [3]: $(\frac{2}{15}) = (\frac{2}{3}) (\frac{2}{5})$ .
$(\frac{2}{3})$ : $3 \equiv 3 (mod 8) \Rightarrow - 1$ . $(\frac{2}{5})$ : $5 \equiv 5 (mod 8) \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:

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

This is the defining limitation of the Jacobi symbol.

Common Misconceptions

The Jacobi symbol does NOT test quadratic residuosity for composite $n$ .

(\frac{a}{n}) = - 1

does guarantee

a

is a non-residue (since at least one local Legendre factor is

- 1

). But

(\frac{a}{n}) = + 1

guarantees nothing: it only says an even number of local factors are

- 1

. True residuosity mod

n

requires

(\frac{a}{p}) = + 1

for every prime

p ∣ n

, which the single value

\pm 1

cannot encode. Denominator must be odd and positive in the classical Jacobi symbol. Expressions like

(\frac{3}{4})

(\frac{5}{- 7})

are undefined as Jacobi symbols. To handle even or negative bottoms, switch to the Kronecker Symbol, which sets

(\frac{a}{2}) = (- 1)^{(a^{2} - 1) /8}

and

(\frac{a}{- 1}) = sgn (a)

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

Connections

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 $Z$ and packages Jacobi symbols into the theory of real Dirichlet characters $χ_{d} (\cdot) = (\frac{d}{\cdot})$ , 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.

Real-World Applications

Solovay–Strassen primality test: A probabilistic test checking whether $(\frac{a}{n}) \equiv a^{(n - 1) /2} (mod n)$ for random $a$ . Composites fail for at least half of all $a$ (Euler witnesses), giving error $\leq 2^{- k}$ after $k$ trials. The test crucially uses Jacobi's factorization-free evaluation.
Goldwasser–Micali cryptosystem: The first probabilistic public-key encryption, whose security rests on the quadratic residuosity problem — distinguishing residues from non-residues with Jacobi symbol $+ 1$ modulo $n = pq$ , which is believed hard without factoring $n$ .
Blum–Blum–Shub pseudorandom generator: Iterates $x \mapsto x^{2} mod n$ with Jacobi-symbol-based output bits, secure under the residuosity assumption.
Cocks identity-based encryption (2001): Uses Jacobi symbols modulo an RSA composite to encode identities, an early IBE scheme.
Cipolla / Tonelli–Shanks square-root algorithms: Use Legendre/Jacobi symbols to detect solvability of $x^{2} \equiv a$ before extracting roots, essential in elliptic-curve point compression.
Lucas–Lehmer and Lucas pseudoprime tests: Choose parameters via $(\frac{D}{n}) = - 1$ (Selfridge's method) in the strong Baillie–PSW primality test used in major math libraries (GMP, SageMath, Mathematica).
Computational number theory libraries: Fast Jacobi-symbol routines (binary-GCD-style, $O (lo g^{2} n)$ ) are core primitives in PARI/GP, FLINT, and OpenSSL's bignum code.

Historical Development

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 $\pm 1$ 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.

Subtleties & Limits

The quadratic residuosity problem (QRP) — given $n = pq$ and $a$ with $(\frac{a}{n}) = + 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 (lo g^{2} p)$ and unconditional ones $O (p^{1/4 + ϵ})$ (Burgess) is a long-standing open question.

Jacobi Symbol and Generalized Reciprocity

The Core Insight

Formal Statement

Legendre Symbol

Jacobi Symbol

Fundamental Properties

Why It Holds / Derivation

Reciprocity from the Sign Lemma

Carl Gustav Jacob Jacobi | 1804–1851

Building Intuition

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

Worked Examples

Evaluating a Jacobi symbol by reciprocity

The symbol fails to detect a residue

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads