If n = p1^e1 x ... x pk^ek, then (a/n) = product (a/pi)^ei
Reduction uses quadratic reciprocity
The Jacobi symbol extends the Legendre symbol from prime moduli to odd composite moduli. It is computed through modular reductions and reciprocity rules, without fully requiring prime factorization.
⚠n must be positive and odd. A Jacobi value of 1 is only a necessary condition for quadratic residuosity when n is composite.
What Is the Jacobi Symbol?
The Jacobi symbol is a compact number theory value used to reason about quadratic residues with odd moduli. It is especially useful in algorithms where factoring n is expensive.
Odd Modulus
The denominator n must be positive and odd.
Three Values
The result is 1, -1, or 0.
Composite Warning
Value 1 does not guarantee a square root for composite n.
Algorithm Use
Jacobi symbols appear in primality tests and reciprocity problems.
Example: For a = 1001 and n = 9907, reduce a modulo n and apply Jacobi reciprocity rules until the symbol value is found.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.