# 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)).