Jacobi symbol

The Jacobi symbol (a/n) is a multiplicative function of an integer numerator and an odd positive denominator, defined by multiplying Legendre symbols according to the prime factors of the denominator. It generalizes the Legendre symbol, but a value of 1 does not always mean the numerator is a quadratic residue modulo the denominator.

Legendre symbol: A function that indicates whether an integer is a quadratic residue modulo an odd prime, with values 1, −1, or 0. Each prime factor contributes a Legendre symbol to the Jacobi symbol’s defining product.
Quadratic residue: An integer congruent to a square modulo a given modulus. The Jacobi symbol is designed to encode quadratic-residue information, though imperfectly for composite moduli.
Solovay–Strassen primality test: A randomized primality test based on Euler’s criterion and the Jacobi symbol. The test compares a modular power with a Jacobi-symbol value to detect compositeness.
Euler pseudoprime: A composite integer that satisfies an Euler-style congruence for a chosen base despite not being prime. Such composites can pass tests using Jacobi symbols, illustrating that the symbol alone cannot certify primality.
Quadratic reciprocity: A theorem relating whether two odd primes are quadratic residues modulo one another. Reciprocity laws let computations exchange numerator and denominator, driving efficient Jacobi-symbol algorithms.
Modular arithmetic: Arithmetic in which integers are identified when they have the same remainder modulo a fixed positive integer. Residues and congruences provide the setting for interpreting the symbol’s numerator.
Euler's criterion: A formula relating a prime-modulus power of an integer to its Legendre symbol. Its Jacobi-symbol analogue underlies the congruence checked by Solovay–Strassen.
Carmichael number: A composite integer that satisfies Fermat’s little theorem congruence for every base relatively prime to it. These composites expose the limits of primality tests built from residue congruences.
Supplementary laws of quadratic reciprocity: Formulas giving quadratic-residue information for −1 and 2 modulo odd primes. These formulas supply the sign changes needed when reciprocity-based evaluation encounters −1 or 2.
Prime factorization: The expression of an integer as a product of primes, unique up to the order of factors. The denominator’s prime factorization determines which Legendre symbols are multiplied.

Linked from 7 pages