Jacobi symbol

related topics
{math, number, function}
{@card@, make, design}

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837,[1] it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

Contents

Definition

For any integer a and any positive odd integer n the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of n:


(\tfrac{a}{p}) represents the Legendre symbol, defined for all integers a and all odd primes p by

Following the normal convention for the empty product, \Bigg(\frac{a}{1}\Bigg) = 1.

Properties

These facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol.[2]

Keep in mind that Jacobi symbols are only defined when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.

The law of quadratic reciprocity: if m and n are odd positive coprime integers, then

and its supplements

Like the Legendre symbol,

But, unlike the Legendre symbol

This is because for a to be a residue (mod n) it has to be a residue modulo every prime that divides n, but the Jacobi symbol will equal one if for example a is a non-residue for exactly two of the primes which divide n.

Calculating the Jacobi symbol

The above formulas lead to an efficient[3] algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the GCD of two numbers. (This should not be surprising in light of rule 3)).

Full article ▸

related documents
Stirling's approximation
Free variables and bound variables
Sylow theorems
Associative algebra
Perfect number
Chain complex
Elliptic integral
Diophantine equation
Compact space
1 (number)
Pauli matrices
Bolzano–Weierstrass theorem
Integral domain
Cumulative distribution function
Generating trigonometric tables
Monotone convergence theorem
Cotangent space
Linear subspace
Column space
Compactness theorem
Operator overloading
Quasigroup
Interpolation search
Measure (mathematics)
Special linear group
Borel algebra
Union (set theory)
Graftal
Golden ratio base
Automata theory