The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, 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.
Definition For any integer a and any positive odd integer n, the Jacobi symbol (a/n) is defined as the product of the Legendre symbols corresponding to the prime factors of n:
( a n ) := ( a p 1 ) α 1 ( a p 2 ) α 2 ⋯ ( a p k ) α k , {\displaystyle \left({\frac {a}{n}}\right):=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},}
where
n = p 1 α 1 p 2 α 2 ⋯ p k α k {\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}
is the prime factorization of n. The Legendre symbol (a/p) is defined for all integers a and all odd primes p by
( a p ) := { 0 if a ≡ 0 ( mod p ) , 1 if a ≢ 0 ( mod p ) and for some integer x : a ≡ x 2 ( mod p ) , − 1 if a ≢ 0 ( mod p ) and there is no such x . {\displaystyle \left({\frac {a}{p}}\right):=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.}
Following the normal convention for the empty product, (a/1) = 1. When the lower argument is an odd prime, the Jacobi symbol is equal to the Legendre symbol.
Table of values The following is a table of values of Jacobi symbol (a/n) with n ≤ 59, a ≤ 30, n odd.
Properties The following facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol. The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.
… excerpt ends here. Continue reading the full article.
