The Jacobi Symbol

Suppose you want to know whether x2≡8137(mod5959)x^2 \equiv 8137 \pmod{5959} has a solution. However, 5959=59×1015959 = 59 \times 101 is composite. You have no quick way to factor it. The Legendre Symbol only makes sense for a prime modulus. So it cannot be applied directly to 59595959. Yet the formula that computes Legendre symbols via The Law of Quadratic Reciprocity looks purely combinatorial. It flips numerator and denominator with a sign correction. This almost begs to be extended past primality. The Jacobi symbol is exactly this extension. It is a multiplicative bookkeeping device defined for any odd positive denominator. It is built by multiplying Legendre symbols over the prime factorization. The payoff is enormous. Reciprocity for the Jacobi symbol lets us compute (an)\left(\frac{a}{n}\right) for huge aa and odd nn. We use an algorithm that looks exactly like the Euclidean algorithm. It is a sequence of reductions and flips. This runs in time polynomial in log⁡n\log n, without ever factoring nn. This is remarkable for one key reason. The Legendre symbol's own defining property (quadratic residue or not) genuinely depends on primality. Yet the Jacobi symbol strips this dependency away from the computation. It does this while sacrificing part of its meaning. A Jacobi symbol of +1+1 no longer certifies that aa is a square mod nn. The big picture is this. The Jacobi symbol is a completely multiplicative function on the group of integers coprime to nn. It agrees with the Legendre symbol prime by prime. It also satisfies its own reciprocity law. This law mirrors quadratic reciprocity almost verbatim. This makes it the natural setting for fast primality tests (Solovay–Strassen). It also suits the definition of pseudosquares in cryptography. And it enables a cleaner theoretical treatment of quadratic forms over composite moduli. This article gives the precise definition and proves complete multiplicativity. It proves the three supplementary laws and the reciprocity law in full. It works two nontrivial numerical examples. It shows exactly where the Jacobi symbol fails to detect quadratic residues. This is the price paid for its computational freedom. It closes by pointing toward the algorithmic and cryptographic uses. These uses make this symbol indispensable in practice.

⚡ Key Takeaways
  • The Jacobi symbol (an)\left(\frac{a}{n}\right) extends the Legendre symbol to any odd n>0n>0 by multiplying over nn's prime factors.
  • It is completely multiplicative in both the top and bottom arguments (for odd, coprime, positive denominators).
  • It satisfies its own reciprocity law: for odd coprime m,n>0m,n>0, (mn)(nm)=(−1)m−12n−12\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}.
  • Supplementary laws for −1-1 and 22 hold in exactly the same form as for the Legendre symbol.
  • Crucially, (an)=1\left(\frac{a}{n}\right)=1 does not imply aa is a quadratic residue mod nn when nn is composite.
  • Key idea: factoring out primality lets reciprocity become a fast recursive algorithm, at the cost of losing the residue-detection meaning.
DefinitionThe Jacobi Symbol

Let nn be a positive odd integer with prime factorization

n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}

(where the pip_i are distinct primes, possibly k=0k=0 giving n=1n=1), and let aa be any integer. The Jacobi symbol (an)\left(\dfrac{a}{n}\right) is defined by

(an)  =  ∏i=1k(api)ei,\left(\frac{a}{n}\right) \;=\; \prod_{i=1}^{k} \left(\frac{a}{p_i}\right)^{e_i},

where each factor (api)\left(\frac{a}{p_i}\right) is the ordinary Legendre Symbol. By convention (a1)=1\left(\frac{a}{1}\right) = 1 for every aa (the empty product). Thus the Jacobi symbol takes values in {−1,0,1}\{-1, 0, 1\}: it is 00 if and only if gcd⁡(a,n)>1\gcd(a,n) > 1, and otherwise it is ±1\pm 1.

Intuition

The definition is deliberately naive: to evaluate (an)\left(\frac{a}{n}\right), factor nn and multiply Legendre symbols. This immediately shows the symbol is 11 whenever aa is an actual quadratic residue mod nn (with gcd⁡(a,n)=1\gcd(a,n)=1), because each prime-power Legendre-symbol factor is forced to be 11 when aa is a square mod each pip_i. But the converse fails: the symbol can be +1+1 by an even number of −1-1 factors canceling, without aa being a square mod any of the individual primes dividing nn. This is the central subtlety of the whole theory, and it is why the Jacobi symbol is a computational tool rather than a residue-detector once nn is composite. The deeper reason the symbol is useful despite this is that its multiplicativity and reciprocity properties hold unconditionally, regardless of what is happening internally with residues. The proof of Jacobi reciprocity reduces cleanly to the prime case via a careful additivity argument on the exponents p−12\frac{p-1}{2} and p2−18\frac{p^2-1}{8} that appear in the Legendre supplementary laws — the whole engineering effort of this article is checking that these exponents behave well modulo 2 under multiplication of odd numbers, so that products of prime factorizations reciprocate coherently.

Figure
Jacobi symbol as a signed product over prime factors, illustrated for n = 21 = 3·7
(a/21) = (a/3)·(a/7), example a = 5 (5/3) 5 ≡ 2 mod 3 2 is non-residue: −1 (5/7) squares mod 7: 1,4,2 5 not among them: −1 (5/21) (−1)·(−1) = +1 Note: 5 is NOT a square mod 3, NOT a square mod 7 — yet (5/21) = +1. Symbol +1 does not certify a residue.
TheoremComplete Multiplicativity and Reciprocity of the Jacobi Symbol

Let m,nm, n be positive odd integers and a,ba, b integers.

(1) Multiplicativity in the top: (abn)=(an)(bn)\left(\dfrac{ab}{n}\right) = \left(\dfrac{a}{n}\right)\left(\dfrac{b}{n}\right).

(2) Multiplicativity in the bottom: (amn)=(am)(an)\left(\dfrac{a}{mn}\right) = \left(\dfrac{a}{m}\right)\left(\dfrac{a}{n}\right).

(3) Supplementary law for −1-1: if gcd⁡(a,n)=1\gcd(a,n)=1 is not required here since nn itself determines this;

(−1n)=(−1)n−12.\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}.

(4) Supplementary law for 22:

(2n)=(−1)n2−18.\left(\frac{2}{n}\right) = (-1)^{\frac{n^2-1}{8}}.

(5) Reciprocity: if in addition gcd⁡(m,n)=1\gcd(m,n) = 1, then

(mn)(nm)=(−1)m−12⋅n−12.\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}.
LemmaAdditivity of the reciprocity exponent modulo 2

Define ε(n)=n−12  2\varepsilon(n) = \frac{n-1}{2} \bmod 2 and ω(n)=n2−18  2\omega(n) = \frac{n^2-1}{8} \bmod 2 for odd positive nn. Then for odd positive m,nm,n:

ε(mn)≡ε(m)+ε(n)(mod2),ω(mn)≡ω(m)+ω(n)(mod2).\varepsilon(mn) \equiv \varepsilon(m) + \varepsilon(n) \pmod 2, \qquad \omega(mn) \equiv \omega(m) + \omega(n) \pmod 2.

Equivalently, (−1)mn−12=(−1)m−12(−1)n−12(-1)^{\frac{mn-1}{2}} = (-1)^{\frac{m-1}{2}}(-1)^{\frac{n-1}{2}} and (−1)(mn)2−18=(−1)m2−18(−1)n2−18(-1)^{\frac{(mn)^2-1}{8}} = (-1)^{\frac{m^2-1}{8}}(-1)^{\frac{n^2-1}{8}}.

Proof

Technique: direct algebraic identity via writing m=1+2sm = 1+2s, n=1+2tn=1+2t. Write m=1+2sm = 1+2s and n=1+2tn = 1+2t with s,ts,t integers (since m,nm,n are odd). Then

mn−1=(1+2s)(1+2t)−1=2s+2t+4st,mn - 1 = (1+2s)(1+2t) - 1 = 2s + 2t + 4st,

so

mn−12=s+t+2st≡s+t=m−12+n−12(mod2).\frac{mn-1}{2} = s + t + 2st \equiv s+t = \frac{m-1}{2} + \frac{n-1}{2} \pmod 2.

This proves the first identity, since reducing an exponent of −1-1 modulo 2 does not change the value (−1)(⋅)(-1)^{(\cdot)}. For the second identity, we use the standard fact that for any odd integer kk, k2≡1(mod16)k^2 \equiv 1 \pmod{16} (proof: k=2j+1k=2j+1, so k2−1=4j(j+1)k^2 - 1 = 4j(j+1), and j(j+1)j(j+1) is even, so 4j(j+1)4j(j+1) is divisible by 88; in fact one checks k2≡1(mod8)k^2\equiv 1\pmod 8 directly and the sharper mod-16 fact is not needed — we redo this cleanly below). Actually we only need k2−18  2\frac{k^2-1}{8} \bmod 2, i.e. k2−1  16k^2 - 1 \bmod 16. Let k=2j+1k = 2j+1. Then k2−1=4j(j+1)k^2 - 1 = 4j(j+1). Since j(j+1)j(j+1) is always even (product of consecutive integers), write j(j+1)=2rj(j+1) = 2r; then k2−1=8rk^2-1 = 8r, so k2−18=r=j(j+1)2\frac{k^2-1}{8} = r = \frac{j(j+1)}{2}, which is the jj-th triangular number TjT_j. We must show Tm′:=(mn)2−18≡m2−18+n2−18(mod2)T_m' := \frac{(mn)^2-1}{8} \equiv \frac{m^2-1}{8} + \frac{n^2-1}{8} \pmod 2. Compute directly:

(mn)2−1=m2n2−1=(m2−1)(n2−1)+(m2−1)+(n2−1).(mn)^2 - 1 = m^2n^2 - 1 = (m^2-1)(n^2-1) + (m^2 - 1) + (n^2-1).

Divide by 8:

(mn)2−18=(m2−1)(n2−1)8+m2−18+n2−18.\frac{(mn)^2-1}{8} = \frac{(m^2-1)(n^2-1)}{8} + \frac{m^2-1}{8} + \frac{n^2-1}{8}.

Since m,nm,n are odd, 8∣(m2−1)8 \mid (m^2-1) and 8∣(n2−1)8\mid (n^2-1) (as shown: m2−18=Tj\frac{m^2-1}{8}=T_j is an integer), so (m2−1)(n2−1)(m^2-1)(n^2-1) is divisible by 6464, hence (m2−1)(n2−1)8\frac{(m^2-1)(n^2-1)}{8} is divisible by 88, in particular even. Therefore modulo 2,

(mn)2−18≡m2−18+n2−18(mod2),\frac{(mn)^2-1}{8} \equiv \frac{m^2-1}{8} + \frac{n^2-1}{8} \pmod 2,

as required. ■\blacksquare

∎
Proof

Proof of the Theorem. Technique: reduction to the Legendre symbol case via prime factorization, using multiplicativity of both the symbol and the reciprocity exponent (previous lemma). Write n=∏i=1kpiein = \prod_{i=1}^k p_i^{e_i} and, when needed, m=∏j=1ℓqjfjm = \prod_{j=1}^\ell q_j^{f_j}, with pi,qjp_i, q_j odd primes.

(1) Multiplicativity in the top. By definition,

(abn)=∏i=1k(abpi)ei.\left(\frac{ab}{n}\right) = \prod_{i=1}^k \left(\frac{ab}{p_i}\right)^{e_i}.

For each prime pip_i, the Legendre symbol is completely multiplicative: (abpi)=(api)(bpi)\left(\frac{ab}{p_i}\right) = \left(\frac{a}{p_i}\right)\left(\frac{b}{p_i}\right). This is a standard property of the Legendre symbol, provable via Euler's criterion (ap)≡a(p−1)/2(modp)\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p, since (ab)(p−1)/2=a(p−1)/2b(p−1)/2(ab)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}. Substituting,

(abn)=∏i(api)ei(bpi)ei=(∏i(api)ei)(∏i(bpi)ei)=(an)(bn).\left(\frac{ab}{n}\right) = \prod_i \left(\frac{a}{p_i}\right)^{e_i}\left(\frac{b}{p_i}\right)^{e_i} = \left(\prod_i \left(\frac{a}{p_i}\right)^{e_i}\right)\left(\prod_i \left(\frac{b}{p_i}\right)^{e_i}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right).

(2) Multiplicativity in the bottom. The prime factorization of mnmn is the "concatenation" of the factorizations of mm and nn (multiply exponents of shared primes if gcd⁡(m,n)>1\gcd(m,n)>1; if gcd⁡(m,n)=1\gcd(m,n)=1 the prime sets are disjoint, but the argument works regardless since the Jacobi symbol definition is literally a product over the multiset of prime-power factors). Precisely, if mn=∏ipiei∏jqjfjmn = \prod_{i} p_i^{e_i} \prod_j q_j^{f_j} (merging exponents where primes coincide), then by definition

(amn)=∏i(api)ei⋅∏j(aqj)fj=(am)(an),\left(\frac{a}{mn}\right) = \prod_i \left(\frac{a}{p_i}\right)^{e_i} \cdot \prod_j \left(\frac{a}{q_j}\right)^{f_j} = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right),

directly from the definition applied separately to mm and to nn, since the definition of (an)\left(\frac a n\right) only depends on the multiset of prime-power factors of nn and multiplies Legendre-symbol contributions independently for each. No property of the Legendre symbol beyond its own definition is needed here; this is purely a statement about how the defining product behaves under merging factorizations.

(3) Supplementary law for −1-1. By definition and the known Legendre-symbol supplementary law (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} (a standard consequence of Euler's criterion, part of The Law of Quadratic Reciprocity package),

(−1n)=∏i=1k(−1pi)ei=∏i=1k[(−1)pi−12]ei=(−1)∑iei⋅pi−12.\left(\frac{-1}{n}\right) = \prod_{i=1}^k \left(\frac{-1}{p_i}\right)^{e_i} = \prod_{i=1}^k \left[(-1)^{\frac{p_i-1}{2}}\right]^{e_i} = (-1)^{\sum_i e_i \cdot \frac{p_i - 1}{2}}.

We must show ∑ieipi−12≡n−12(mod2)\sum_i e_i \frac{p_i-1}{2} \equiv \frac{n-1}{2} \pmod 2. This follows by repeated application of the additivity lemma: writing nn as a product of eie_i copies of each pip_i (i.e. n=p1⋅p1⋯p1⋅p2⋯n = p_1 \cdot p_1 \cdots p_1 \cdot p_2 \cdots, a product of ∑ei\sum e_i odd primes with repetition), the lemma gives

n−12≡∑iei⋅pi−12(mod2)\frac{n-1}{2} \equiv \sum_i e_i \cdot \frac{p_i - 1}{2} \pmod 2

by induction on the number of factors (base case one factor is trivial; inductive step is exactly the additivity identity of the Lemma applied to "current partial product" times "next prime factor"). Hence (−1n)=(−1)(n−1)/2\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2}.

(4) Supplementary law for 22. Identical argument using the Legendre supplementary law (2p)=(−1)(p2−1)/8\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} and the second part of the additivity Lemma, by the same induction on the factorization of nn into (not necessarily distinct) odd primes:

(2n)=∏i[(−1)pi2−18]ei=(−1)∑ieipi2−18=(−1)n2−18.\left(\frac{2}{n}\right) = \prod_i \left[(-1)^{\frac{p_i^2-1}{8}}\right]^{e_i} = (-1)^{\sum_i e_i \frac{p_i^2-1}{8}} = (-1)^{\frac{n^2-1}{8}}.

(5) Reciprocity. Let m=∏j=1ℓqjfjm = \prod_{j=1}^\ell q_j^{f_j} and n=∏i=1kpiein = \prod_{i=1}^k p_i^{e_i} with gcd⁡(m,n)=1\gcd(m,n)=1, so no qjq_j equals any pip_i. By definition and multiplicativity already established (parts 1–2 applied repeatedly, or directly from the definition):

(mn)(nm)=(∏i(mpi)ei)(∏j(nqj)fj).\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = \left(\prod_{i} \left(\frac{m}{p_i}\right)^{e_i}\right)\left(\prod_j \left(\frac{n}{q_j}\right)^{f_j}\right).

Expand (mpi)=∏j(qjpi)fj\left(\frac{m}{p_i}\right) = \prod_j \left(\frac{q_j}{p_i}\right)^{f_j} (Legendre symbol multiplicativity in the top, as in part 1 but now with the Legendre symbol directly) and similarly (nqj)=∏i(piqj)ei\left(\frac{n}{q_j}\right) = \prod_i \left(\frac{p_i}{q_j}\right)^{e_i}. Substituting,

(mn)(nm)=∏i,j(qjpi)eifj(piqj)eifj=∏i,j[(qjpi)(piqj)]eifj.\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = \prod_{i,j} \left(\frac{q_j}{p_i}\right)^{e_if_j} \left(\frac{p_i}{q_j}\right)^{e_if_j} = \prod_{i,j} \left[\left(\frac{q_j}{p_i}\right)\left(\frac{p_i}{q_j}\right)\right]^{e_if_j}.

Since pi≠qjp_i \neq q_j are distinct odd primes, The Law of Quadratic Reciprocity gives

(qjpi)(piqj)=(−1)pi−12⋅qj−12.\left(\frac{q_j}{p_i}\right)\left(\frac{p_i}{q_j}\right) = (-1)^{\frac{p_i - 1}{2}\cdot\frac{q_j-1}{2}}.

Substituting and combining exponents,

(mn)(nm)=(−1)∑i,jeifj⋅pi−12⋅qj−12=(−1)(∑ieipi−12)(∑jfjqj−12).\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\sum_{i,j} e_if_j \cdot \frac{p_i-1}{2}\cdot\frac{q_j-1}{2}} = (-1)^{\left(\sum_i e_i \frac{p_i-1}{2}\right)\left(\sum_j f_j \frac{q_j-1}{2}\right)}.

By the computation in part (3) above, ∑ieipi−12≡n−12(mod2)\sum_i e_i \frac{p_i-1}{2} \equiv \frac{n-1}{2} \pmod 2 and ∑jfjqj−12≡m−12(mod2)\sum_j f_j\frac{q_j-1}{2} \equiv \frac{m-1}{2}\pmod 2. Since we only care about the exponent modulo 2 (as it exponentiates −1-1), we conclude

(mn)(nm)=(−1)n−12⋅m−12=(−1)m−12⋅n−12.\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{n-1}{2}\cdot\frac{m-1}{2}} = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}.

This completes the proof of all five parts. ■\blacksquare

∎

Worked examples

Example 1: Evaluate (10019907)\left(\dfrac{1001}{9907}\right) where 99079907 is prime, without directly testing quadratic residuosity. First check 99079907 is odd (it is) and that gcd⁡(1001,9907)=1\gcd(1001,9907)=1: factor 1001=7×11×131001 = 7\times 11\times 13, and none of 7,11,137,11,13 divides 99079907 (since 99079907 is prime and larger than each), so the gcd is 11 and the symbol is ±1\pm1. We use the Jacobi-symbol algorithm — reciprocity plus reduction mod the current denominator — even though 99079907 happens to be prime, illustrating that the method doesn't care about primality of either argument. Step 1: (10019907)\left(\dfrac{1001}{9907}\right). Both 10011001 and 99079907 are odd and positive, and coprime, so reciprocity applies. We have 1001≡1(mod4)1001 \equiv 1 \pmod 4 (since 1001=4⋅250+11001 = 4\cdot 250 + 1) — actually let's directly track the sign via the formula (−1)1001−12⋅9907−12(-1)^{\frac{1001-1}{2}\cdot\frac{9907-1}{2}}. Compute 1001−12=500\frac{1001-1}{2} = 500 (even) and 9907−12=4953\frac{9907-1}{2}=4953 (odd). The product 500×4953500 \times 4953 is even (since 500500 is even), so the reciprocity sign is (−1)even=+1(-1)^{\text{even}} = +1. Hence

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

Step 2: Reduce 9907  10019907 \bmod 1001. Compute 9907=9×1001+8989907 = 9\times 1001 + 898 (check: 9×1001=90099\times1001=9009, 9907−9009=8989907-9009=898). So

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

Step 3: Factor out powers of 22: 898=2×449898 = 2 \times 449, and 449449 is odd. So

(8981001)=(21001)(4491001).\left(\frac{898}{1001}\right) = \left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right).

Step 4: Evaluate (21001)=(−1)10012−18\left(\frac{2}{1001}\right) = (-1)^{\frac{1001^2-1}{8}}. Since 1001≡1(mod8)1001 \equiv 1 \pmod 8 (as 1001=8×125+11001 = 8\times 125 + 1), we have 10012≡1(mod16)1001^2 \equiv 1 \pmod{16} hence certainly 10012−18\frac{1001^2-1}{8} is even (the standard supplementary rule states (2n)=1\left(\frac 2 n\right)=1 when n≡±1(mod8)n\equiv \pm 1 \pmod 8). So (21001)=1\left(\frac{2}{1001}\right) = 1. Step 5: Now handle (4491001)\left(\frac{449}{1001}\right), both odd, coprime (since 449449 is prime and does not divide 1001=7×11×131001 = 7\times11\times13). Reciprocity sign: 449−12=224\frac{449-1}{2}=224 (even), so the sign is automatically +1+1 regardless of 10011001's residue mod 4. So

(4491001)=(1001449).\left(\frac{449}{1001}\right) = \left(\frac{1001}{449}\right).

Step 6: Reduce 1001  4491001 \bmod 449: 1001=2×449+1031001 = 2\times 449 + 103 (check: 2×449=8982\times449=898, 1001−898=1031001-898=103). So

(1001449)=(103449).\left(\frac{1001}{449}\right) = \left(\frac{103}{449}\right).

Step 7: Reciprocity again: 103−12=51\frac{103-1}{2}=51 (odd), 449−12=224\frac{449-1}{2}=224 (even); product is even, sign +1+1:

(103449)=(449103).\left(\frac{103}{449}\right) = \left(\frac{449}{103}\right).

Step 8: Reduce 449  103449 \bmod 103: 449=4×103+37449 = 4\times103 + 37 (check: 4×103=4124\times103=412, 449−412=37449-412=37). So

(449103)=(37103).\left(\frac{449}{103}\right) = \left(\frac{37}{103}\right).

Step 9: Reciprocity: 37−12=18\frac{37-1}{2}=18 (even), sign +1+1:

(37103)=(10337).\left(\frac{37}{103}\right) = \left(\frac{103}{37}\right).

Step 10: Reduce 103  37103 \bmod 37: 103=2×37+29103 = 2\times37+29. So

(10337)=(2937).\left(\frac{103}{37}\right) = \left(\frac{29}{37}\right).

Step 11: Reciprocity: 29−12=14\frac{29-1}{2}=14 (even), sign +1+1:

(2937)=(3729).\left(\frac{29}{37}\right) = \left(\frac{37}{29}\right).

Step 12: Reduce 37  29=837 \bmod 29 = 8:

(3729)=(829)=(229)3=(229)\left(\frac{37}{29}\right) = \left(\frac{8}{29}\right) = \left(\frac{2}{29}\right)^3 = \left(\frac{2}{29}\right)

(since 8=238=2^3 and cubing a value in {−1,1}\{-1,1\} preserves it). Step 13: (229)=(−1)(292−1)/8\left(\frac{2}{29}\right) = (-1)^{(29^2-1)/8}. Since 29≡5(mod8)29 \equiv 5\pmod 8, the standard rule gives (229)=−1\left(\frac 2{29}\right)=-1 (rule: (2n)=−1\left(\frac2n\right)=-1 when n≡3,5(mod8)n \equiv 3,5 \pmod 8). Let's double check via the formula: 292−1=84029^2-1 = 840, 840/8=105840/8=105, which is odd, so (−1)105=−1(-1)^{105}=-1. Confirmed. Tracing back: every reciprocity sign used above was +1+1, and the only sign contribution is this final −1-1. So

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

This tells us 10011001 is a quadratic non-residue mod the prime 99079907 — and since 99079907 is prime, this conclusion is fully justified (unlike in composite-modulus cases).

Example 2: Evaluate (158235)\left(\dfrac{158}{235}\right) where 235=5×47235 = 5\times 47 is composite, and compare direct factorization with the reciprocity algorithm. Check validity: 235235 is odd. gcd⁡(158,235)\gcd(158,235): 158=2×79158 = 2\times79, and 235=5×47235=5\times47 share no common factor with 158158, so gcd is 11. Method A: direct factorization. (158235)=(1585)(15847)\left(\frac{158}{235}\right) = \left(\frac{158}{5}\right)\left(\frac{158}{47}\right). 158≡3(mod5)158 \equiv 3 \pmod 5 (since 158=31×5+3158 = 31\times5+3). Squares mod 55 are {1,4}\{1,4\}; 33 is not among them, so (1585)=(35)=−1\left(\frac{158}{5}\right) = \left(\frac 35\right) = -1. 158≡158−3×47=158−141=17(mod47)158 \equiv 158 - 3\times47 = 158-141=17 \pmod{47}. We need (1747)\left(\frac{17}{47}\right). Use reciprocity (both primes, 17≡1(mod4)17\equiv1\pmod4, so sign automatically +1+1 regardless): (1747)=(4717)\left(\frac{17}{47}\right) = \left(\frac{47}{17}\right). Reduce 47  17=47−2×17=1347 \bmod 17 = 47-2\times17=13. So (4717)=(1317)\left(\frac{47}{17}\right)=\left(\frac{13}{17}\right). Reciprocity: 13≡1(mod4)13\equiv1\pmod4 so sign +1+1: (1317)=(1713)\left(\frac{13}{17}\right)=\left(\frac{17}{13}\right). Reduce 17  13=417\bmod13=4: (1713)=(413)=(213)2=1\left(\frac{17}{13}\right)=\left(\frac4{13}\right)=\left(\frac2{13}\right)^2=1 (any nonzero square is +1+1, since squaring ±1\pm1 gives 11). So (1747)=1\left(\frac{17}{47}\right)=1, hence (15847)=1\left(\frac{158}{47}\right) = 1. Therefore (158235)=(−1)(1)=−1\left(\frac{158}{235}\right) = (-1)(1) = -1. Method B: Jacobi reciprocity directly on 235235 without factoring. (158235)\left(\frac{158}{235}\right): first pull out the factor of 22: 158=2×79158=2\times79, so

(158235)=(2235)(79235).\left(\frac{158}{235}\right) = \left(\frac{2}{235}\right)\left(\frac{79}{235}\right).

(2235)=(−1)(2352−1)/8\left(\frac2{235}\right)=(-1)^{(235^2-1)/8}. Since 235≡3(mod8)235 \equiv 3\pmod 8 (as 235=29×8+3235=29\times8+3), the rule gives (2235)=−1\left(\frac2{235}\right)=-1. Now (79235)\left(\frac{79}{235}\right): reciprocity sign (−1)79−12⋅235−12=(−1)39×117(-1)^{\frac{79-1}2\cdot\frac{235-1}2} = (-1)^{39\times117}; both 3939 and 117117 are odd so the product is odd, sign is −1-1. So

(79235)=−(23579).\left(\frac{79}{235}\right) = -\left(\frac{235}{79}\right).

Reduce 235  79235 \bmod 79: 235=2×79+77235 = 2\times79+77, so (23579)=(7779)\left(\frac{235}{79}\right)=\left(\frac{77}{79}\right). Factor 77=7×1177=7\times11: (7779)=(779)(1179)\left(\frac{77}{79}\right) = \left(\frac7{79}\right)\left(\frac{11}{79}\right). (779)\left(\frac7{79}\right): reciprocity sign (−1)7−12⋅79−12=(−1)3×39(-1)^{\frac{7-1}2\cdot\frac{79-1}2}=(-1)^{3\times39}, odd times odd is odd, sign −1-1: (779)=−(797)\left(\frac7{79}\right)=-\left(\frac{79}7\right). Reduce 79  7=279\bmod7=2: (797)=(27)\left(\frac{79}7\right)=\left(\frac27\right). Since 7≡7(mod8)7\equiv7\pmod8, rule gives (27)=1\left(\frac27\right)=1. So (779)=−1\left(\frac7{79}\right)=-1. (1179)\left(\frac{11}{79}\right): reciprocity sign (−1)5×39(-1)^{5\times39}, odd, sign −1-1: (1179)=−(7911)\left(\frac{11}{79}\right) = -\left(\frac{79}{11}\right). Reduce 79  11=79−7×11=279\bmod11=79-7\times11=2. (7911)=(211)\left(\frac{79}{11}\right)=\left(\frac2{11}\right). Since 11≡3(mod8)11\equiv3\pmod8, rule gives −1-1. So (7911)=−1\left(\frac{79}{11}\right)=-1, hence (1179)=−(−1)=1\left(\frac{11}{79}\right) = -(-1)=1. So (7779)=(−1)(1)=−1\left(\frac{77}{79}\right) = (-1)(1) = -1, thus (23579)=−1\left(\frac{235}{79}\right) = -1, thus (79235)=−(−1)=1\left(\frac{79}{235}\right) = -(-1) = 1. Finally (158235)=(2235)(79235)=(−1)(1)=−1\left(\frac{158}{235}\right) = \left(\frac2{235}\right)\left(\frac{79}{235}\right) = (-1)(1) = -1. Both methods agree: (158235)=−1\left(\dfrac{158}{235}\right) = -1. Since the symbol is −1-1, we can immediately conclude 158158 is not a square mod 235235 (a −1-1 value always correctly certifies non-residuosity — this direction never fails, as we prove below). The subtlety only arises when the symbol equals +1+1.

CounterexampleWhy coprimality with the modulus, and why +1+1 cannot certify residuosity, is essential

The reciprocity theorem requires gcd⁡(m,n)=1\gcd(m,n)=1; dropping this makes the formula meaningless (the symbol may be 00 and the exponent identity has no residue-theoretic content). But the more instructive failure, central to why the Jacobi symbol is not simply "a bigger Legendre symbol," is this: the implication "(an)=1\left(\frac an\right)=1 and gcd⁡(a,n)=1\gcd(a,n)=1 ⇒\Rightarrow aa is a square mod nn" is false for composite nn. Take n=15=3×5n = 15 = 3\times5 and a=2a = 2. Compute

(215)=(23)(25).\left(\frac2{15}\right) = \left(\frac23\right)\left(\frac25\right).

Squares mod 33 are {1}\{1\} (nonzero residues 1,21,2; 12=1,22=11^2=1,2^2=1), so 22 is a non-residue mod 33: (23)=−1\left(\frac23\right)=-1. Squares mod 55 are {1,4}\{1,4\}; 22 is not among them, so (25)=−1\left(\frac25\right)=-1. Hence

(215)=(−1)(−1)=1.\left(\frac2{15}\right) = (-1)(-1) = 1.

Yet 22 is a quadratic non-residue mod both 33 and mod 55 individually, and by the Chinese Remainder Theorem, x2≡2(mod15)x^2\equiv2\pmod{15} has a solution if and only if x2≡2x^2\equiv2 has a solution mod 33 and mod 55 simultaneously — which it does not, since it fails mod 33 already. So 22 is not a square mod 1515, despite (215)=+1\left(\frac2{15}\right)=+1. This shows precisely what breaks: the Legendre symbol's residue-detection meaning relies on Z/pZ\mathbb{Z}/p\mathbb{Z} being a field, where the squares form an index-22 subgroup of (Z/pZ)×(\mathbb Z/p\mathbb Z)^\times and Euler's criterion converts symbol value into an exact residue test. For composite nn, (Z/nZ)×(\mathbb Z/n\mathbb Z)^\times splits (by CRT) into a product of the prime-power unit groups, and "being a square in the product" requires being a square in every factor — a much stronger condition than the product of signs being +1+1. The Jacobi symbol only ever sees the product of signs, so it cannot distinguish "even number of non-residue factors" from "residue in every factor." Note carefully what does not break: if (an)=−1\left(\frac a n\right) = -1, then some prime factor pieip_i^{e_i} of nn must contribute (api)ei=−1\left(\frac{a}{p_i}\right)^{e_i} = -1 to the product, and in particular (api)=−1\left(\frac{a}{p_i}\right)=-1 for that prime (with eie_i odd), so aa is a non-residue mod pip_i, hence aa cannot be a square mod nn (again by CRT, since it already fails at one prime power). So the one-directional implication "(an)=−1⇒a\left(\frac an\right)=-1 \Rightarrow a is a non-residue mod nn" remains true; only the converse direction (from +1+1) fails.

Scope, edge cases & common traps

SituationWhat holdsWhat can fail
nn primeJacobi symbol = Legendre symbol exactlynothing — full residue-detection meaning holds
nn composite, symbol =−1=-1aa is provably a non-residue mod nnnone; this direction is always valid
nn composite, symbol =+1=+1multiplicativity/reciprocity still holddoes not imply aa is a residue mod nn
gcd⁡(m,n)>1\gcd(m,n)>1symbol is 00reciprocity formula is vacuous/inapplicable
nn even or negativeundefined in this article's conventionsome texts extend to negative or even nn with extra care; formulas must be re-derived
⚠️ The classic error

The most common mistake is treating (an)=1\left(\frac an\right)=1 for composite nn as proof that x2≡a(modn)x^2\equiv a\pmod n is solvable. It is only a necessary condition, never sufficient, once nn has more than one distinct prime factor (or a repeated prime factor with an odd total multiplicity contribution can also mask things). Always remember: the Jacobi symbol answers a question about a signed product, not a genuine existential quantifier over solutions, unless the denominator is prime.

The mathematician behind it

CG
Carl Gustav Jacob Jacobi
1804–1851 · 19th-century Prussia (Königsberg and Berlin)

Jacobi was one of the most prolific mathematicians of the 19th century, renowned for foundational work on elliptic functions, the theory of determinants (the Jacobian), and dynamics (Hamilton–Jacobi theory). His introduction of the generalized symbol bearing his name, in an 1837 paper extending Gauss and Legendre's work on quadratic residues, was a small but structurally important piece of his broader program of turning number-theoretic identities into computational and algebraic machinery, a hallmark of his mathematical style across many fields.

⏳ History
- 1801: Gauss publishes Disquisitiones Arithmeticae, proving quadratic reciprocity and developing the residue framework the Jacobi symbol will later generalize.
- 1798: Legendre introduces the symbol (ap)\left(\frac ap\right) that bears his name, in his own attempted proof of reciprocity.
- 1837: Jacobi introduces the generalized symbol for composite odd denominators, proving its multiplicativity and reciprocity properties.
- 1914: The Jacobi symbol becomes a standard computational tool as algorithmic number theory develops alongside early primality-testing ideas.
- 1977: Solovay and Strassen publish their probabilistic primality test built directly on efficient Jacobi symbol computation.

Where this lives today

The Jacobi symbol's chief modern role is computational: because it can be evaluated in O((log⁡n)2)O((\log n)^2) bit operations via a Euclidean-style recursive algorithm (exactly mirroring the worked examples above), it gives a fast way to compute Legendre symbols for large primes without needing to run Euler's criterion (which would require modular exponentiation, itself efficient but structurally different) — the two methods cross-check each other in implementations. This same fast evaluation underlies the Solovay–Strassen primality test, a foundational randomized algorithm in Cryptography and complexity theory: for a candidate prime nn, one checks whether a(n−1)/2≡(an)(modn)a^{(n-1)/2} \equiv \left(\frac an\right) \pmod n for random aa, exploiting the counterexample phenomenon above (composite nn will often fail this check because the Jacobi symbol's +1+1 verdict does not match true residue behavior). In cryptography, the gap this article highlights — that (an)=1\left(\frac an\right)=1 does not imply aa is a square mod nn — is not a bug but a feature exploited constructively: it defines the notion of a pseudosquare, an integer with Jacobi symbol +1+1 that is nevertheless not a quadratic residue. The hardness of distinguishing true squares from pseudosquares modulo an RSA-like composite (the quadratic residuosity problem) underlies the semantic security of the Goldwasser–Micali public-key cryptosystem, one of the first schemes proven secure under a precise cryptographic hardness assumption. Beyond cryptography, the Jacobi symbol appears throughout analytic and algebraic number theory: in the theory of binary Quadratic Forms and their composition, in class field theory as a prototype for more general power-residue symbols (cubic and higher-order reciprocity), and in the study of character sums, where (⋅n)\left(\frac{\cdot}{n}\right) is used as a real Dirichlet character modulo nn when nn is not a perfect square, feeding into LL-functions and the analytic study of quadratic fields.

Ask the tutor: How does the Solovay–Strassen test use Euler's criterion together with fast Jacobi symbol computation to detect compositeness efficiently?

Is the Jacobi symbol defined when nn is even or negative?

The classical definition given here requires nn to be a positive odd integer, matching the article's convention. Many textbooks extend the definition to negative odd nn using (a−n)\left(\frac{a}{-n}\right) conventions tied to the sign of aa, and some extend to n=0n=0 or specific even cases with care, but these extensions require re-deriving multiplicativity and reciprocity from scratch since the proofs above rely essentially on unique factorization into odd primes and on the additivity lemma for n−12\frac{n-1}2 and n2−18\frac{n^2-1}8, both of which assume nn odd and positive. Within this article's scope, always assume n>0n>0 and odd; consult specialized references before using extended conventions elsewhere.

Why does the Jacobi symbol equal the Legendre symbol when nn is prime?

When n=pn=p is an odd prime, the factorization n=p1e1⋯pkekn = p_1^{e_1}\cdots p_k^{e_k} in the definition collapses to the single term p1p^1, so the defining product ∏i(api)ei\prod_i \left(\frac a{p_i}\right)^{e_i} has exactly one factor: (ap)1=(ap)\left(\frac ap\right)^1 = \left(\frac ap\right). So the Jacobi symbol reduces to exactly the Legendre symbol in this case, with no discrepancy — this is why all the supplementary laws and reciprocity look identical in form to their Legendre-symbol counterparts, since they must specialize correctly when nn happens to be prime.

Can the Jacobi symbol ever be used to prove nn is composite?

Yes, and this is precisely the mechanism behind the Solovay–Strassen primality test. If nn is an odd prime, then Euler's criterion guarantees a(n−1)/2≡(an)(modn)a^{(n-1)/2} \equiv \left(\frac an\right) \pmod n for every aa coprime to nn. If one computes both sides for a random aa and finds they disagree, then nn cannot be prime (the criterion, applicable to Legendre symbols of primes, must have failed, so nn is composite), giving a probabilistic compositeness witness without needing to factor nn.

Does (an)=1\left(\frac an\right)=1 ever have any residue-related meaning for composite nn?

It has a precise but weaker meaning: it says the number of prime-power factors pieip_i^{e_i} of nn for which aa is a non-residue mod pip_i, counted with the parity of eie_i, is even. By the Chinese Remainder Theorem this is strictly weaker than "aa is a residue mod every prime power factor of nn," which is the actual condition for aa to be a square mod nn (when gcd⁡(a,n)=1\gcd(a,n)=1). The gap between these two conditions is exactly what defines a pseudosquare, discussed in the cryptography applications above.

How is the Jacobi symbol actually computed efficiently in practice?

The algorithm mirrors the worked examples: repeatedly extract factors of 2 from the numerator using the supplementary law for 2, then apply reciprocity to swap numerator and denominator (tracking the sign via m−12⋅n−12  2\frac{m-1}2\cdot\frac{n-1}2 \bmod 2, which only needs m,n  4m,n \bmod 4), then reduce the new numerator modulo the new denominator, and repeat. This is essentially the binary/Euclidean GCD algorithm with sign bookkeeping, running in O((log⁡n)2)O((\log n)^2) bit operations (or faster with binary-GCD-style optimizations), entirely avoiding factorization of either argument.

Is the Jacobi symbol a group homomorphism?

Yes, in the following precise sense: for fixed odd n>0n>0, the map a↦(an)a \mapsto \left(\frac an\right) restricted to (Z/nZ)×(\mathbb Z/n\mathbb Z)^\times (integers coprime to nn) is a group homomorphism into {±1}\{\pm1\}, by the multiplicativity property proved above. This makes it a real-valued Dirichlet character modulo nn (when nn is not a perfect square, it is a nontrivial character), which is the perspective used in analytic number theory when studying LL-functions attached to quadratic fields.

What role does the additivity lemma for n−12\frac{n-1}2 and n2−18\frac{n^2-1}8 play, conceptually?

It is the technical hinge that lets the entire theorem reduce to the prime case. Because Jacobi symbol identities are defined via products over prime factorizations, and because the Legendre-symbol supplementary laws and reciprocity law involve exponents p−12\frac{p-1}2 and p2−18\frac{p^2-1}8, one needs these exponents to combine additively (mod 2) when primes are multiplied together into a composite nn. Without this lemma, there would be no way to lift the prime-based reciprocity law to a genuine composite-denominator statement; with it, the lift is mechanical.

Before this