Jacobi symbol#Calculating the Jacobi symbol

{{short description|Generalization of the Legendre symbol in number theory}}

File:Carl_Jacobi.jpg who introduced the symbol.]]

class="wikitable" style="width:500px; text-align:right" ! {{diagonal split header\|n\|k}} !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16
1 \|style="background:#fafa6a"\| 1 \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\|
3 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\|
5 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\|
7 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| −1 \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\|
9 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| 1 \|\| 0 \|\|style="background:#fafa6a"\| 1 \|\| 1 \|\| 0 \|\|style="background:#fafa6a"\| 1 \|\| 1 \|\| \|\| \|\| \|\| \|\| \|\| \|\| \|\|
11 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| −1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| \|\| \|\| \|\| \|\| \|\|
13 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\| −1 \|\| −1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\| \|\| \|\| \|\|
15 \|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 1 \|\| 1 \|\| 0 \|\|style="background:#fafa6a"\| 1 \|\| 0 \|\|style="background:#fafa6a"\| 0 \|\| −1 \|\| 1 \|\|style="background:#fafa6a"\| 0 \|\|style="background:#fafa6a"\| 0 \|\| −1 \|\| 0 \|\| −1\|\| −1\|\| \|\|
17 \|style="background:#fafa6a"\| {{0\|−}}0 \|\|style="background:#fafa6a"\| {{0\|−}}1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| {{0\|−}}1 \|\| −1 \|\| −1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| {{0\|−}}1 \|\| −1 \|\| −1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\| −1 \|\|style="background:#fafa6a"\| 1 \|\|style="background:#fafa6a"\| 1

class="wikitable" style="width:500px; text-align:right"

! {{diagonal split header|n|k}} !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16

1

|style="background:#fafa6a"| 1 || || || || || || || || || || || || || || || ||

3

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 || || || || || || || || || || || || || ||

5

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 || −1 ||style="background:#fafa6a"| 1 || || || || || || || || || || || ||

7

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 || −1 || −1 || || || || || || || || || ||

9

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 1 || || || || || || || ||

11

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 || −1 || || || || || ||

13

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 || || || ||

15

|style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 1 || 1 || 0 ||style="background:#fafa6a"| 1 || 0 ||style="background:#fafa6a"| 0 || −1 || 1 ||style="background:#fafa6a"| 0 ||style="background:#fafa6a"| 0 || −1 || 0 || −1|| −1|| ||

17

|style="background:#fafa6a"| {{0|−}}0 ||style="background:#fafa6a"| {{0|−}}1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| {{0|−}}1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| {{0|−}}1 || −1 || −1 || −1 ||style="background:#fafa6a"| 1 || −1 ||style="background:#fafa6a"| 1 ||style="background:#fafa6a"| 1

Jacobi symbol {{big|(}}{{sfrac|k|n}}{{big|)}} for various k (along top) and n (along left side). Only {{nowrap|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 {{nowrap|1={{big|(}}{{sfrac|k|n}}{{big|)}} = 1}}, but not all entries with a Jacobi symbol of 1 (see the {{nowrap|1=n = 9}} and {{nowrap|1=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,{{cite journal|first=C. G. J.|last=Jacobi|title=Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie|journal=Bericht Ak. Wiss. Berlin|date=1837|pages=127–136}} 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 {{big|(}}{{sfrac|a|n}}{{big|)}} is defined as the product of the Legendre symbols corresponding to the prime factors of n:

: $\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^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

is the prime factorization of n.

The Legendre symbol {{big|(}}{{sfrac|a|p}}{{big|)}} is defined for all integers a and all odd primes p by

: $\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, {{big|(}}{{sfrac|a|1}}{{big|)}} = 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 {{big|(}}{{sfrac|a|n}}{{big|)}} with n ≤ 59, a ≤ 30, n odd.

class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align: right" !{{diagonal split header\|n\|a}} !1 !2 !3 !4 !5 !6 !7 !8 !9 !10 !11 !12 !13 !14 !15 !16 !17 !18 !19 !20 !21 !22 !23 !24 !25 !26 !27 !28 !29 !30
1 \|style="background:#ffccff"\|{{0\|−}}1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|{{0\|−}}1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|{{0\|−}}1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|{{0\|−}}1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|{{0\|−}}1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1
3 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
5 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
7 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1
9 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
11 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1
13 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1
15 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
17 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1
19 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1
21 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
23 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1
25 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
27 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
29 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1
31 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1
33 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
35 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
37 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1
39 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
41 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1
43 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1
45 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
47 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1
49 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1
51 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
53 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1
55 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0
57 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffffcc"\|0 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffffcc"\|0
59 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1 \|style="background:#ccffff"\|−1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ffccff"\|1 \|style="background:#ccffff"\|−1

class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align: right"

!{{diagonal split header|n|a}}

!1

!2

!3

!4

!5

!6

!7

!8

!9

!10

!11

!12

!13

!14

!15

!16

!17

!18

!19

!20

!21

!22

!23

!24

!25

!26

!27

!28

!29

!30

1

|style="background:#ffccff"|{{0|−}}1

|style="background:#ffccff"|1

|style="background:#ffccff"|{{0|−}}1

|style="background:#ffccff"|1

|style="background:#ffccff"|{{0|−}}1

|style="background:#ffccff"|1

|style="background:#ffccff"|{{0|−}}1

|style="background:#ffccff"|1

|style="background:#ffccff"|{{0|−}}1

|style="background:#ffccff"|1

3

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

5

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

7

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

9

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

11

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

13

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

15

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

17

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

19

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

21

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

23

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

25

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

27

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

29

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

31

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

33

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

35

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

37

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

39

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

41

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

43

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

45

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

47

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

49

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

51

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

53

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

55

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

57

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffffcc"|0

|style="background:#ffccff"|1

|style="background:#ffffcc"|0

59

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

|style="background:#ffccff"|1

|style="background:#ccffff"|−1

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.Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10

The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.

:1. If n is (an odd) prime, then the Jacobi symbol {{big|(}}{{sfrac|a|n}}{{big|)}} is equal to (and written the same as) the corresponding Legendre symbol.

:2. If {{nowrap|a ≡ b (mod n)}}, then $\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right) = \left(\frac{a \pm m \cdot n}{n}\right)$

:3. $\left(\frac{a}{n}\right) =
\begin{cases}
0 & \text{if } \gcd(a,n) \ne 1,\\
\pm1 & \text{if } \gcd(a,n) = 1.
\end{cases}$

If either the top or bottom argument is fixed, the Jacobi symbol is a completely multiplicative function in the remaining argument:

:4. $\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right),\quad\text{so } \left(\frac{a^2}{n}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ or } 0.$

:5. $\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right),\quad\text{so } \left(\frac{a}{n^2}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ or } 0.$

The law of quadratic reciprocity: if m and n are odd positive coprime integers, then

:6. $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\tfrac{n-1}{2}} =
\begin{cases}
1 & \text{if } n \equiv 1 \pmod 4 \text{ or } m \equiv 1 \pmod 4,\\
-1 & \text{if } n\equiv m \equiv 3 \pmod 4
\end{cases}$

and its supplements

:7. $\left(\frac{-1}{n}\right) = (-1)^\tfrac{n-1}{2} =
\begin{cases}
1 & \text{if }n \equiv 1 \pmod 4,\\
-1 & \text{if }n \equiv 3 \pmod 4,
\end{cases}$ ,

and $\left(\frac{1}{n}\right) = \left(\frac{n}{1}\right) = 1$

:8. $\left(\frac{2}{n}\right) = (-1)^\tfrac{n^2-1}{8} =
\begin{cases} 1 & \text{if }n \equiv 1,7 \pmod 8,\\
-1 & \text{if }n \equiv 3,5\pmod 8.
\end{cases}$

Combining properties 4 and 8 gives:

:9. $\left(\frac{2a}{n}\right) = \left(\frac{2}{n}\right) \left(\frac{a}{n}\right) =
\begin{cases} \left(\frac{a}{n}\right) & \text{if }n \equiv 1,7 \pmod 8,\\
{-\left(\frac{a}{n}\right)} & \text{if }n \equiv 3,5\pmod 8.
\end{cases}$

Like the Legendre symbol:

If {{big|(}}{{sfrac|a|n}}{{big|)}} = −1 then a is a quadratic nonresidue modulo n.

If a is a quadratic residue modulo n and gcd(a,n) = 1, then {{big|(}}{{sfrac|a|n}}{{big|)}} = 1.

But, unlike the Legendre symbol:

:If {{big|(}}{{sfrac|a|n}}{{big|)}} = 1 then a may or may not be a quadratic residue modulo n.

This is because for a to be a quadratic residue modulo n, it has to be a quadratic residue modulo every prime factor of n. However, the Jacobi symbol equals one if, for example, a is a non-residue modulo exactly two of the prime factors of n.

Although the Jacobi symbol cannot be uniformly interpreted in terms of squares and non-squares, it can be uniformly interpreted as the sign of a permutation by Zolotarev's lemma.

The Jacobi symbol {{big|(}}{{sfrac|a|n}}{{big|)}} is a Dirichlet character to the modulus n.

Calculating the Jacobi symbol

The above formulas lead to an efficient {{nowrap|O(log a log b)}}Cohen, pp. 29–31 algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the gcd of two numbers. (This should not be surprising in light of rule 2.)

Reduce the "numerator" modulo the "denominator" using rule 2.
Extract any even "numerator" using rule 9.
If the "numerator" is 1, rules 3 and 4 give a result of 1. If the "numerator" and "denominator" are not coprime, rule 3 gives a result of 0.
Otherwise, the "numerator" and "denominator" are now odd positive coprime integers, so we can flip the symbol using rule 6, then return to step 1.

In addition to the codes below, Rieselp. 285 has it in Pascal.

=Implementation in [[Lua (programming language)|Lua]]=

function jacobi(n, k)

assert(k > 0 and k % 2 == 1)

n = n % k

t = 1

while n ~= 0 do

while n % 2 == 0 do

n = n / 2

r = k % 8

if r == 3 or r == 5 then

t = -t

end

n, k = k, n

if n % 4 == 3 and k % 4 == 3 then

t = -t

end

n = n % k

end

if k == 1 then

return t

else

return 0

end

= Implementation in [[C++]] =

// a/n is represented as (a,n)

int jacobi(int a, int n) {

assert(n > 0 && n%2 == 1);

// Step 1

a = (a % n + n) % n; // Handle (a < 0)

// Step 3

int t = 0; // XOR of bits 1 and 2 determines sign of return value

while (a != 0) {

// Step 2

while (a % 4 == 0)

a /= 4;

if (a % 2 == 0) {

t ^= n; // Could be "^= n & 6"; we only care about bits 1 and 2

a /= 2;

}

// Step 4

t ^= a & n & 2; // Flip sign if a % 4 == n % 4 == 3

int r = n % a;

n = a;

a = r;

}

if (n != 1)

return 0;

else if ((t ^ (t >> 1)) & 2)

return -1;

else

return 1;

}

Example of calculations

The Legendre symbol {{big|(}}{{sfrac|a|p}}{{big|)}} is only defined for odd primes p. It obeys the same rules as the Jacobi symbol (i.e., reciprocity and the supplementary formulas for {{big|(}}{{sfrac|−1|p}}{{big|)}} and {{big|(}}{{sfrac|2|p}}{{big|)}} and multiplicativity of the "numerator".)

Problem: Given that 9907 is prime, calculate {{big|(}}{{sfrac|1001|9907}}{{big|)}}.

=Using the Legendre symbol=

: $\begin{align}
\left(\frac{1001}{9907}\right)
&=\left(\frac{7}{9907}\right) \left(\frac{11}{9907}\right) \left(\frac{13}{9907}\right).
\\
\left(\frac{7}{9907}\right)
&=-\left(\frac{9907}{7}\right)
=-\left(\frac{2}{7}\right)
=-1.
\\
\left(\frac{11}{9907}\right)
&=-\left(\frac{9907}{11}\right)
=-\left(\frac{7}{11}\right)
=\left(\frac{11}{7}\right)
=\left(\frac{4}{7}\right)
=1.
\\
\left(\frac{13}{9907}\right)
&=\left(\frac{9907}{13}\right)
=\left(\frac{1}{13}\right)
=1.
\\
\left(\frac{1001}{9907}\right) &=-1. \end{align}$

=Using the Jacobi symbol=

: $\begin{align}
\left(\frac{1001}{9907}\right)
&=\left(\frac{9907}{1001}\right)
=\left(\frac{898}{1001}\right)
=\left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right)
=\left(\frac{449}{1001}\right)
\\
&=\left(\frac{1001}{449}\right)
=\left(\frac{103}{449}\right)
=\left(\frac{449}{103}\right)
=\left(\frac{37}{103}\right)
=\left(\frac{103}{37}\right)
\\
&=\left(\frac{29}{37}\right)
=\left(\frac{37}{29}\right)
=\left(\frac{8}{29}\right)
=\left(\frac{2}{29}\right)^3
=-1.
\end{align}$

The difference between the two calculations is that when the Legendre symbol is used the "numerator" has to be factored into prime powers before the symbol is flipped. This makes the calculation using the Legendre symbol significantly slower than the one using the Jacobi symbol, as there is no known polynomial-time algorithm for factoring integers.The number field sieve, the fastest known algorithm, requires

: $O\left(e^{(\ln N)^\frac13(\ln\ln N)^\frac23\big(C+o(1)\big)}\right)$

operations to factor n. See Cohen, p. 495 In fact, this is why Jacobi introduced the symbol.

Primality testing

There is another way the Jacobi and Legendre symbols differ. If the Euler's criterion formula is used modulo a composite number, the result may or may not be the value of the Jacobi symbol, and in fact may not even be −1 or 1. For example,

: $\begin{align}
\left(\frac{19}{45}\right) &= 1 &&\text{ and } & 19^\frac{45-1}{2} &\equiv 1\pmod{45}. \\
\left(\frac{ 8}{21}\right) &= -1 &&\text{ but } & 8^\frac{21-1}{2} &\equiv 1\pmod{21}. \\
\left(\frac{ 5}{21}\right) &= 1 &&\text{ but } & 5^\frac{21-1}{2} &\equiv 16\pmod{21}.
\end{align}$

So if it is unknown whether a number n is prime or composite, we can pick a random number a, calculate the Jacobi symbol {{big|(}}{{sfrac|a|n}}{{big|)}} and compare it with Euler's formula; if they differ modulo n, then n is composite; if they have the same residue modulo n for many different values of a, then n is "probably prime".

This is the basis for the probabilistic Solovay–Strassen primality test and refinements such as the Baillie–PSW primality test and the Miller–Rabin primality test.

As an indirect use, it is possible to use it as an error detection routine during the execution of the Lucas–Lehmer primality test which, even on modern computer hardware, can take weeks to complete when processing Mersenne numbers over $\begin{align}2^{136,279,841} - 1\end{align}$ (the largest known Mersenne prime as of October 2024). In nominal cases, the Jacobi symbol:

$\begin{align}\left(\frac{s_i - 2}{M_p}\right) &= -1 & i \ne 0\end{align}$

This also holds for the final residue $\begin{align}s_{p-2}\end{align}$ and hence can be used as a verification of probable validity. However, if an error occurs in the hardware, there is a 50% chance that the result will become 0 or 1 instead, and won't change with subsequent terms of $\begin{align}s\end{align}$ (unless another error occurs and changes it back to −1).

Notes

References

{{cite book

| last1 = Cohen | first1 = Henri

| title = A Course in Computational Algebraic Number Theory

| publisher = Springer

| location = Berlin

| date = 1993

| isbn = 3-540-55640-0}}

{{cite book

| last1 = Ireland | first1 = Kenneth

| last2 = Rosen | first2 = Michael

| title = A Classical Introduction to Modern Number Theory

| publisher = Springer

| location = New York

| date = 1990

| isbn = 0-387-97329-X

| edition = Second

}}

{{cite book

| last1 = Lemmermeyer | first1 = Franz

| title = Reciprocity Laws: from Euler to Eisenstein

| publisher = Springer

| location = Berlin

| date = 2000

| isbn = 3-540-66957-4}}

{{citation

| last1 = Riesel | first1 = Hans

| title = Prime Numbers and Computer Methods for Factorization (second edition)

| publisher = Birkhäuser

| location = Boston

| date = 1994

| isbn = 0-8176-3743-5}}

{{cite journal

| title = On the Worst Case of Three Algorithms for Computing the Jacobi Symbol

| first = Jeffrey | last = Shallit | author-link = Jeffrey Shallit

| journal = Journal of Symbolic Computation

| date = December 1990 | volume = 10 | issue = 6 | pages = 593–61

| url = https://digitalcommons.dartmouth.edu/cs_tr/42/

| doi = 10.1016/S0747-7171(08)80160-5 | id = Computer science technical report PCS-TR89-140

| doi-access = free}}

{{cite tech report

| title = Average-case analyses of three algorithms for computing the Jacobi symbol

| first1 = Brigitte | last1 = Vallée | author-link1=Brigitte Vallée

| first2 = Charly | last2 = Lemée

| date = October 1998

| citeseerx = 10.1.1.32.3425

| url = https://vallee.users.greyc.fr/Publications/jacobi.ps

}}

{{cite journal

| title = Efficient Algorithms for Computing the Jacobi Symbol

| first1 = Shawna Meyer | last1 = Eikenberry

| first2 = Jonathan P. | last2 = Sorenson

| journal = Journal of Symbolic Computation

| volume = 26 | issue = 4 | pages = 509–523 | date = October 1998

| doi = 10.1006/jsco.1998.0226 | citeseerx = 10.1.1.44.2423

| url = https://core.ac.uk/download/pdf/82664209.pdf

}}

External links

[http://math.fau.edu/richman/jacobi.htm Calculate Jacobi symbol] {{Webarchive|url=https://web.archive.org/web/20161005150500/http://math.fau.edu/richman/jacobi.htm |date=2016-10-05 }} shows the steps of the calculation.

Category:Modular arithmetic

Jacobi symbol#Calculating the Jacobi symbol

Definition

Table of values

Properties

Calculating the Jacobi symbol

=Implementation in [[Lua (programming language)|Lua]]=

= Implementation in [[C++]] =

Example of calculations

=Using the Legendre symbol=

=Using the Jacobi symbol=

Primality testing

See also

Notes

References

External links