Editing Jacobi symbol

{{short description|Generalization of the Legendre symbol in number theory}}
[[File:Carl_Jacobi.jpg | thumb | 220x124px | right | [[Carl Gustav Jacob Jacobi]] who introduced the symbol.]]
<div class="thumb tright">
<div class="thumbinner" style="width:500px;">
{| 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
|}
<div class="thumbcaption">
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 residue]]s are highlighted in yellow &mdash; 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.
</div>
</div>
</div>
The '''Jacobi symbol''' is a generalization of the [[Legendre symbol]]. Introduced by [[Carl Gustav Jakob Jacobi|Jacobi]] in 1837,<ref>{{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}}</ref> 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 symbol]]s corresponding to the prime factors of ''n'':
:<math>\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},</math>
where
:<math>n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math>
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
:<math>\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.</math>

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''&nbsp;≤&nbsp;59, ''a''&nbsp;≤&nbsp;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
|}

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

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'' &nbsp;(mod ''n'')}}, then <math>\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)  = \left(\frac{a \pm m \cdot n}{n}\right)</math>

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

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

:4. <math>\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.</math>

:5. <math>\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.</math>

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

:6. <math>\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}
</math> 

and its supplements

:7. <math>\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}
</math>, 

and <math>\left(\frac{1}{n}\right) = \left(\frac{n}{1}\right) = 1
</math>

:8. <math>\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}
</math>

Combining properties 4 and 8 gives:

:9. <math>
\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}
</math>

Like the Legendre symbol:

*If {{big|(}}{{sfrac|''a''|''n''}}{{big|)}}&nbsp;=&nbsp;−1 then ''a'' is a quadratic nonresidue modulo ''n''.

*If ''a'' is a [[quadratic residue]] modulo ''n'' and [[greatest common divisor|gcd]](''a'',''n'')&nbsp;=&nbsp;1, then {{big|(}}{{sfrac|''a''|''n''}}{{big|)}}&nbsp;=&nbsp;1.

But, unlike the Legendre symbol:

:If {{big|(}}{{sfrac|''a''|''n''}}{{big|)}}&nbsp;=&nbsp;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|[[Big O notation|''O'']](log ''a'' log ''b'')}}<ref>Cohen, pp. 29–31</ref> [[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, Riesel<ref>p. 285</ref> has it in [[Pascal (programming language)|Pascal]].
===Implementation in [[Lua (programming language)|Lua]]===
<syntaxhighlight lang="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
    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
end
</syntaxhighlight>

=== Implementation in [[C++]] ===
<syntaxhighlight lang="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;
}
</syntaxhighlight>

==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===

:<math>\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}</math>

===Using the Jacobi symbol===

:<math>\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}</math>

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.<ref>The [[General number field sieve|number field sieve]], the fastest known algorithm, requires
:<math>O\left(e^{(\ln N)^\frac13(\ln\ln N)^\frac23\big(C+o(1)\big)}\right)</math>
operations  to factor ''n''. See Cohen, p. 495</ref> 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,

:<math>\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}</math>

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 "[[Probable prime|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 number]]s over <math>\begin{align}2^{136,279,841} - 1\end{align}</math> (the largest known Mersenne prime as of October 2024). In nominal cases, the Jacobi symbol:

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

This also holds for the final residue <math>\begin{align}s_{p-2}\end{align}</math> 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 <math>\begin{align}s\end{align}</math> (unless another error occurs and changes it back to −1).

==See also==

*[[Kronecker symbol]], a generalization of the Jacobi symbol to all integers.
*[[Power residue symbol]], a generalization of the Jacobi symbol to higher powers residues.

==Notes==

{{reflist}}

==References==
*{{cite book
  | last1 = Cohen  | first1 = Henri
  | title = A Course in Computational Algebraic Number Theory
  | publisher = [[Springer Science+Business Media|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 Science+Business Media|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 Science+Business Media|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]]