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ₖ:
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
Prime Factorization of 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.
Help us improve!
How would you rate the Jacobi Symbol Calculator?
Editorial Note
MyCalcBuddy Editorial Team
This page is maintained as an educational calculator reference.
Formula Source: Handbook of Mathematical Functions
by Abramowitz & Stegun