Jacobi symbol


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.


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:


is the prime factorization of n.

The Legendre symbol (a/p) is defined for all integers a and all odd primes p by

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