The Jacobi Symbol

Number Theory · Axiom Academy

Generalizing the Legendre symbol to composite moduli 1. Definition via Prime Factorization The Jacobi symbol generalizes the Legendre symbol by using the prime factorization of the modulus. where (a/pᵢ) denotes the Legendre symbol. Each Legendre symbol evaluates to -1, 0, or +1. Let's compute the Jacobi symbol (2/15) using the prime factorization 15 = 3 × 5. We evaluate each Legendre symbol separately: (2/3) = -1 (since 2 is not a quadratic residue mod 3) (2/5) = -1 (since 2 is not a quadratic residue mod 5) Therefore: (2/15) = (-1) × (-1) = +1 The Jacobi symbol inherits many useful properties from the Legendre symbol, making it computationally efficient. These properties allow us to compute Jacobi symbols efficiently using the same reciprocity-based algorithm used for Legendre symbols. The Jacobi symbol can be computed without factoring the modulus, making it extremely efficient for large numbers.

This is the written version of the interactive lesson above. See the full Number Theory course.