Carl Gustav Jacob Jacobi · Leopold Kronecker
\[\left(\tfrac{a}{n}\right)\]
\[\left(\frac{a}{n}\right)=\prod_{i=1}^{k}\left(\frac{a}{p_{i}}\right)^{e_{i}}\qquad\text{for}\qquad n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\]
The three symbols form a tower of successive generalizations of the same object. The Legendre symbol \(\left(\tfrac{a}{p}\right)\) is defined only for an odd prime \(p\). The Jacobi symbol extends it to any odd \(n>0\) by multiplying the Legendre symbols of the prime factors of \(n\). The Kronecker symbol extends it further to every integer lower argument, including \(n=2\) and \(n<0\), via the supplementary values :
\[\left(\frac{a}{2}\right)=\begin{cases}0 & a\ \text{even}\\ +1 & a\equiv \pm 1 \pmod 8\\ -1 & a\equiv \pm 3 \pmod 8\end{cases}\qquad\left(\frac{a}{-1}\right)=\begin{cases}+1 & a\geq 0\\ -1 & a<0\end{cases}\]
A316569 Jacobi symbol (n/15) : the tower's first genuinely composite modulus.
A091337 Kronecker symbol (8/n) : period 0,1,0,-1,0,-1,0,1.
A034947 Kronecker symbol (-1/n) : the Jacobi sign sequence.
# Legendre, Jacobi and Kronecker in Sage : one tower
# Legendre (a/7) : lower argument is an odd prime
print [legendre_symbol(a, 7) for a in range(1, 8)] # 1,1,-1,1,-1,-1,0
# Jacobi (a/15) : lower argument odd composite = product over prime factors
print [jacobi_symbol(a, 15) for a in range(1, 16)] # 1,1,0,1,0,0,-1,1,0,0,-1,0,-1,-1,0
# For an odd prime the Jacobi symbol coincides with Legendre
print [jacobi_symbol(a, 7) for a in range(1, 8)] == [legendre_symbol(a, 7) for a in range(1, 8)]
# Kronecker extends to every lower argument, including 2 and negatives
print [kronecker_symbol(8, n) for n in range(1, 9)] # (8/n)
print [kronecker_symbol(-1, n) for n in range(1, 21)] # (-1/n)
\[\left(\frac{2}{15}\right)=+1\qquad\text{yet}\qquad 2\ \text{is NOT a quadratic residue mod }15\]
For the Legendre symbol with prime \(p\), the value \(+1\) means exactly that \(a\) is a quadratic residue. This equivalence breaks for the Jacobi symbol at composite \(n\) : a value of \(-1\) still guarantees \(a\) is a non-residue, but a value of \(+1\) no longer guarantees a residue. The residues mod \(15\) are \(\{1,4,6,9,10\}\), which does not contain \(2\), even though \(\left(\tfrac{2}{15}\right)=(+1)(+1)=(-1)(-1)=+1\) as a product of two \((-1)\) Legendre factors. This is precisely why the Solovay–Strassen primality test works : composite “liars” are caught through this mismatch.
# The composite caveat : Jacobi = +1 does not imply quadratic residue
n = 15
print jacobi_symbol(2, n) # +1
residues = sorted(set((x^2) % n for x in range(n)))
print residues # [0, 1, 4, 6, 9, 10]
print 2 in residues # False -> a liar
# But Jacobi = -1 ALWAYS certifies a non-residue (never lies that way)
print [a for a in range(1, n) if jacobi_symbol(a, n) == -1 and gcd(a, n) == 1]
The Jacobi symbol obeys the same reciprocity law as Legendre, which is what makes it computable by repeated flipping without any factorization. For odd coprime \(m,n>0\) :
\[\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\cdot \frac{n-1}{2}}\]
with the two supplementary laws :
\[\left(\frac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}\qquad\qquad \left(\frac{2}{n}\right)=(-1)^{\frac{n^{2}-1}{8}}\]
Each such symbol \(n\mapsto \left(\tfrac{a}{n}\right)\) is a real Dirichlet character, tying this page back to the quadratic L-functions.
# Quadratic reciprocity for the Jacobi symbol (odd coprime m, n > 0)
for (m, n) in [(5,9), (7,15), (11,21), (13,25)]:
lhs = jacobi_symbol(m, n) * jacobi_symbol(n, m)
rhs = (-1)^( ((m-1)//2) * ((n-1)//2) )
print m, n, lhs, rhs, lhs == rhs
# Supplementary laws
for n in [3,5,7,9,11,13,15]:
print n, jacobi_symbol(-1, n), jacobi_symbol(2, n)