The Jacobi Symbol
The Legendre symbol
needs a prime on the bottom. To use
reciprocity
as a fast algorithm we want to flip symbols freely — without stopping to factor. The
Jacobi symbol extends the definition to any odd bottom and makes exactly that
possible.
Definition
For an odd n = p_1 p_2 \cdots p_k (with repetition), the Jacobi symbol
is the product of Legendre symbols over its prime factors:
\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_k}\right).
When n is itself prime, it coincides with the Legendre symbol — so it is
a genuine generalisation.
A crucial caveat
- If \left(\frac{a}{n}\right) = -1, then a is definitely not a square modulo n.
- If \left(\frac{a}{n}\right) = +1, then a may or may not be a square.
The failure case: \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right)\left(\frac{2}{5}\right) = (-1)(-1) = +1,
yet 2 is not a square mod 15 (a
non-residue times a non-residue gives +1 here without either factor
being a square). So the Jacobi symbol is about computation, not detection.
Why it's worth it
The payoff is huge: the Jacobi symbol obeys the same reciprocity and supplement laws as
Legendre, but its rules can be applied to any odd n — so you flip and
reduce without ever factoring. That gives a fast,
Euclid-like
algorithm for Legendre symbols, and it is the heart of the Solovay–Strassen
primality test.