The Legendre symbol is a beautiful piece of notation — but it comes with a strict rule: the bottom p must be an odd prime. That's a real problem for cryptography. An RSA-style modulus n is a huge odd composite number, often hundreds of digits long, and its factors are deliberately kept secret — finding them is exactly the hard problem the whole system relies on. If "is a a square modulo n?" only made sense for primes, we'd be stuck the moment the bottom stopped being prime.

The Jacobi symbol rescues the notation. It extends \left(\frac{a}{n}\right) to any odd n, prime or not, by declaring it to be the product of Legendre symbols over n's prime factors. The payoff is almost magical: thanks to reciprocity, the Jacobi symbol can be computed quickly using only flipping and reducing — never once factoring n along the way. You get to keep working with a modulus whose factorisation you don't know (or don't want to spend a billion years finding).

Definition

For an odd positive integer n = p_1 p_2 \cdots p_k written as a product of primes (repeated according to multiplicity), the Jacobi symbol is the product of the Legendre symbols at each of those primes:

Two sanity checks fall straight out of the definition. When n is itself prime, the "product" has a single term, so the Jacobi symbol reduces to the ordinary Legendre symbol — it is a genuine generalisation, not a different tool. And by convention \left(\frac{a}{1}\right) = 1 for every a (an empty product). Just like Legendre, the value is always one of +1, -1, or 0 — and it is 0 exactly when \gcd(a, n) > 1, since then some prime factor of n divides a and contributes a zero to the product.

One more subtlety worth noticing early: when a prime appears more than once in n's factorisation, its Legendre symbol gets multiplied by itself, so it contributes an even power. Take n = 9 = 3^2 and a = 2: \left(\frac{2}{9}\right) = \left(\frac{2}{3}\right)^2 = (-1)^2 = +1. That happens regardless of whether 2 is genuinely a square mod 9, and it isn't (the squares mod 9 are 0, 1, 4, 7, and 2 is not among them). A repeated prime factor always forces the Jacobi symbol to +1 (or 0), no matter what a is, simply because squaring a \pm 1 always gives +1. Keep this in mind; it is the first hint that a +1 from the Jacobi symbol can mean much less than it looks like it means.

A worked example

Let's compute \left(\frac{2}{105}\right). First factor the bottom: 105 = 3 \cdot 5 \cdot 7. The definition says multiply the three Legendre symbols:

There's a handy shortcut for \left(\frac{2}{p}\right): it equals +1 exactly when p \equiv \pm 1 \pmod 8, and -1 when p \equiv \pm 3 \pmod 8. Checking each prime:

• 3 \equiv 3 \pmod 8 \Rightarrow \left(\frac{2}{3}\right) = -1
• 5 \equiv 5 \pmod 8 \Rightarrow \left(\frac{2}{5}\right) = -1
• 7 \equiv -1 \pmod 8 \Rightarrow \left(\frac{2}{7}\right) = +1

Multiplying them: (-1)(-1)(+1) = +1. So \left(\frac{2}{105}\right) = +1 — a clean, fast computation, done without ever asking "is 2 actually a square mod 105?" directly. Keep this example close by; it's about to reveal something surprising.

The crucial caveat

Now look back at the example. We found \left(\frac{2}{105}\right) = +1. For 2 to be a genuine square modulo 105 = 3 \cdot 5 \cdot 7, the Chinese Remainder Theorem says it must be a square modulo each prime factor separately — modulo 3, modulo 5, and modulo 7. But we just computed \left(\frac{2}{3}\right) = -1: 2 is not a square mod 3 at all. Two "no"s (at 3 and at 5) multiplied together give a +1, exactly the same +1 you'd get from three genuine "yes"es. The Jacobi symbol simply cannot tell the two situations apart — it only ever sees the product of signs, never the individual votes.

Why it's worth it anyway

You might wonder why anyone bothers with a symbol that can lie about residues. The answer is speed. The Jacobi symbol obeys the same reciprocity and supplement laws as the Legendre symbol, but those rules now apply to any odd n — so you can flip the fraction upside-down and reduce the top modulo the bottom, over and over, exactly like the Euclidean algorithm, without ever factoring anything. For a modulus with hundreds of digits, factoring would take longer than the age of the universe with today's computers; the reciprocity-based algorithm finishes in a fraction of a second. That trade — a slightly weaker guarantee in exchange for enormous speed — turns out to be exactly what a fast Legendre-symbol algorithm, and the Solovay–Strassen primality test, need.

Computing without ever factoring

Here's the promised speed trick in action. Compute \left(\frac{11}{35}\right) using only reciprocity and the supplement rules — pretending, just for this once, that we don't already know 35 = 5 \cdot 7.

Both 11 and 35 are odd and coprime, so reciprocity applies: \left(\frac{11}{35}\right)\left(\frac{35}{11}\right) = (-1)^{\frac{11-1}{2}\cdot\frac{35-1}{2}} = (-1)^{5 \cdot 17} = -1. Since both symbols are \pm 1, that means \left(\frac{11}{35}\right) = -\left(\frac{35}{11}\right). Now reduce the top of the flipped symbol modulo 11: 35 \equiv 2 \pmod{11}, so \left(\frac{35}{11}\right) = \left(\frac{2}{11}\right). The supplement rule for 2 says this is -1 whenever the bottom is \equiv \pm 3 \pmod 8; here 11 \equiv 3 \pmod 8, so \left(\frac{2}{11}\right) = -1. Putting it together:

Not a single factor of 35 was needed — just flipping, reducing, and one supplement rule, exactly like running the Euclidean algorithm. As a check, factoring the honest way confirms it: 11 \bmod 5 = 1 is a perfect square, and 11 \bmod 7 = 4 = 2^2 is too, so \left(\frac{11}{5}\right)\left(\frac{11}{7}\right) = (+1)(+1) = +1 — the same answer, reached the slow way. For a modulus with two small prime factors either route is fine; for a modulus with hundreds of digits, only the reciprocity route is remotely possible.