# Jacobi symbol

k
n
012345678910111213141516
11
301−1
501−1−11
7011−11−1−1
9011011011
1101−1111−1−1−11−1
1301−111−1−1−1−111−11
150110100−1100−10−1−1
17011−11−1−1−111−1−1−11−111

Jacobi symbol (k/n) for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then (k/n) = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 and n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative.

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.

## 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:

${\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

${\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

${\displaystyle \left({\frac {a}{p}}\right)=\left\\right.}$

Following the normal convention for the empty product, (a/1) = 1.

The Legendre and Jacobi symbols are indistinguishable exactly when the lower argument is an odd prime, in which case they have the same value.

Other Languages
čeština: Jacobiho symbol
Deutsch: Jacobi-Symbol
Esperanto: Jakobia simbolo
한국어: 야코비 기호
Nederlands: Jacobi-symbool
ភាសាខ្មែរ: សញ្ញាយ៉ាកូប៊ី
português: Símbolo de Jacobi
русский: Символ Якоби
Türkçe: Jacobi sembolü
українська: Символ Якобі
Tiếng Việt: Kí hiệu Jacobi