Jacobi symbol

k 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 (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.

^ Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin: 127–136.

[1] Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin: 127–136.

[1]