Jacobi symbol

m
n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1
3 0 1 −1
5 0 1 −1 −1 1
7 0 1 1 −1 1 −1 −1
9 0 1 1 0 1 1 0 1 1
11 0 1 −1 1 1 1 −1 −1 −1 1 −1
13 0 1 −1 1 1 −1 −1 −1 −1 1 1 −1 1
15 0 1 1 0 1 0 0 −1 1 0 0 −1 0 −1 −1
17 0 1 1 −1 1 −1 −1 −1 1 1 −1 −1 −1 1 −1 1 1

Jacobi symbol (m/n) for various m (along top) and n (along left side). Only 0 ≤ m < n are shown, since due to rule (2) below any other m 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 m is a quadratic residue modulo a coprime n, then (m/n) = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 row) are quadratic residues. Notice also that when either n or m 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:

where

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