Jacobi Symbol Calculator
Calculate the Jacobi symbol (a/n) extending the Legendre symbol to composite moduli.
Enter Values
Definition
For n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ:
(a/n) = (a/p₁)^e₁ × (a/p₂)^e₂ × ... × (a/pₖ)^eₖ
where (a/pᵢ) are Legendre symbols.
Key Properties
- (a/n) = 0, 1, or -1
- (ab/n) = (a/n)(b/n)
- (a/mn) = (a/m)(a/n)
- If (a/n) = -1, then a is not a QR mod n
- If (a/n) = 1, a may or may not be QR mod n
Jacobi Symbol
(1001/9907) = -1
Result
-1
Quadratic Residue?
No
Prime Factorization of 9907
9907
9907 = 9907
Calculation Steps
Reduce: a ≡ 1001 (mod 9907)
Current result: 1
Swap and reduce: (898/1001)
Current result: 1
Factor 2^1: (2/1001) = 1
Current result: 1
Swap and reduce: (103/449)
Current result: 1
Swap and reduce: (37/103)
Current result: 1
Swap and reduce: (29/37)
Current result: 1
Swap and reduce: (8/29)
Current result: 1
Factor 2^3: (2/29) = -1
Current result: -1
a = 1, done
Current result: -1
Important Note
Unlike the Legendre symbol, (a/n) = 1 does NOT guarantee that a is a quadratic residue mod n. However, (a/n) = -1 DOES guarantee that a is NOT a quadratic residue mod n.