Ogled vira Jacobijev simbol

<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
| style="background:#fafa6a" |−1
| style="background:#fafa6a" |1
|−1
| style="background:#fafa6a" |−1
|−1
|−1
|−1
| style="background:#fafa6a" |1
| style="background:#fafa6a" |−1
|−1
|−1
|−1
| style="background:#fafa6a" |1
|−1
| style="background:#fafa6a" |1
| style="background:#fafa6a" |1
|}
<div class="thumbcaption">
Jacobijev simbol  {{Veliko|(}}{{Sfrac|''k''|''n''}}{{Veliko|)}} za različne ''k'' (proti vrhu) in ''n'' (proti levi). Prikazani so samo {{Brez preloma|0 ≤ ''k'' < ''n''}}, saj se zaradi pravila (2) spodaj da zmanjšati ''k'' za modulo ''n''. [[Kvadratni ostanek|Kvadratni ostanki]] so označeni z rumeno &#x2014; oglej si, da noben vnos z Jacobijevim simbolom −1 ni kvadratni ostanek, če pa je ''k'' kvadratni ostanek modula tujega števila ''n'', potem je {{Brez preloma|1={{big|(}}{{sfrac|''k''|''n''}}{{big|)}} = 1}}, a niso vsi vnosi Jacobijevega simbola 1 (glej vrsti {{Brez preloma|1=''n'' = 9}} in {{Brez preloma|1=''n'' = 15}}) kvadratni ostanki. Opazimo tudi, da če je eden izmed ''n'' ali ''k'' kvadrat, so vse vrednosti nenegativne.
</div>
</div>
</div>'''Jacobijev simbol''' je posplošitev [[Legendrov simbol|Legendrovega simbola]]. Uvedel ga je [[Carl Gustav Jakob Jacobi|Jacobi]] leta 1837,<ref>{{Navedi revijo|first=C. G. J.|last=Jacobi|title=Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie|journal=Bericht Ak. Wiss. Berlin|date=1837|page=127–136}}</ref> navezuje pa se na [[Modularna aritmetika|modularno aritmetiko]] in ostale veje [[Teorija števil|teorije števil]], a glavna uporaba pa se nahaja v [[Računalniška teorija števil|računalniški teoriji števil]], še posebej v [[Praštevilski test|praštevilskem testu]] in [[Praštevilski razcep|praštevilskem razcepu]]; te stvari so zelo pomembne v [[Kriptografija|kriptografiji]].

== Definicija ==
Za katerokoli celo število ''a'' in liho naravno število ''n'', je Jacobijev simbol {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}} definiran kot produkt [[Legendrov simbol|Legendrovih simbolov]], ki predstavljajo praštevilski razcep od ''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>

kjer je

: <math>n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math>

praštevilski razcep od ''n''.

Legendrov simbol {{Veliko|(}}{{Sfrac|''a''|''p''}}{{Veliko|)}} je za vsa cela števila ''a'' in vsa liha praštevila ''p'' definiran

:<math>\left(\frac{a}{p}\right) = \left\{
\begin{array}{rl}
0 & \text{če } a \equiv 0 \pmod{p},\\
1 & \text{če } a \not\equiv 0\pmod{p} \text{ in za neko celo število } x\colon\;a\equiv x^2\pmod{p},\\
-1 & \text{če } a \not\equiv 0\pmod{p} \text{ in ne obstaja noben tak } x.
\end{array}
\right.</math>

Po standardnem sporazumu za prazni produkt, velja {{Veliko|(}}{{Sfrac|''a''|1}}{{Veliko|)}} = 1.

Ko je nižji argument liho praštevilo, potem je Jacobijev simbol enak Legendrovem simbolu.

== Tabela vrednosti ==
Sledeča tabela je seznam vseh vrednosti Jacobijevega simbola {{Veliko|(}}{{Sfrac|''k''|''n''}}{{Veliko|)}} za ''n''&nbsp;≤&nbsp;59, ''k''&nbsp;≤&nbsp;30, ''n'' je lih.
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align: right"
!{{diagonal split header|''n''|''k''}}
!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
|−1
|1
|1
|−1
|1
|1
|1
|1
|−1
|1
|1
|1
|1
|1
|1
|−1
|1
|1
|1
|1
|1
|1
|1
|1
|−1
|1
|1
|1
|1
|1
|-
!3
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|-
!5
|1
|−1
|−1
|1
|0
|1
|−1
|−1
|1
|0
|1
|−1
|−1
|1
|0
|1
|−1
|−1
|1
|0
|1
|−1
|−1
|1
|0
|1
|−1
|−1
|1
|0
|-
!7
|1
|1
|−1
|1
|−1
|−1
|0
|1
|1
|−1
|1
|−1
|−1
|0
|1
|1
|−1
|1
|−1
|−1
|0
|1
|1
|−1
|1
|−1
|−1
|0
|1
|1
|-
!9
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|1
|1
|0
|-
!11
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|1
|−1
|0
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|1
|−1
|0
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|-
!13
|1
|−1
|1
|1
|−1
|−1
|−1
|−1
|1
|1
|−1
|1
|0
|1
|−1
|1
|1
|−1
|−1
|−1
|−1
|1
|1
|−1
|1
|0
|1
|−1
|1
|1
|-
!15
|1
|1
|0
|1
|0
|0
|−1
|1
|0
|0
|−1
|0
|−1
|−1
|0
|1
|1
|0
|1
|0
|0
|−1
|1
|0
|0
|−1
|0
|−1
|−1
|0
|-
!17
|1
|1
|−1
|1
|−1
|−1
|−1
|1
|1
|−1
|−1
|−1
|1
|−1
|1
|1
|0
|1
|1
|−1
|1
|−1
|−1
|−1
|1
|1
|−1
|−1
|−1
|1
|-
!19
|1
|−1
|−1
|1
|1
|1
|1
|−1
|1
|−1
|1
|−1
|−1
|−1
|−1
|1
|1
|−1
|0
|1
|−1
|−1
|1
|1
|1
|1
|−1
|1
|−1
|1
|-
!21
|1
|−1
|0
|1
|1
|0
|0
|−1
|0
|−1
|−1
|0
|−1
|0
|0
|1
|1
|0
|−1
|1
|0
|1
|−1
|0
|1
|1
|0
|0
|−1
|0
|-
!23
|1
|1
|1
|1
|−1
|1
|−1
|1
|1
|−1
|−1
|1
|1
|−1
|−1
|1
|−1
|1
|−1
|−1
|−1
|−1
|0
|1
|1
|1
|1
|−1
|1
|−1
|-
!25
|1
|1
|1
|1
|0
|1
|1
|1
|1
|0
|1
|1
|1
|1
|0
|1
|1
|1
|1
|0
|1
|1
|1
|1
|0
|1
|1
|1
|1
|0
|-
!27
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|1
|−1
|0
|-
!29
|1
|−1
|−1
|1
|1
|1
|1
|−1
|1
|−1
|−1
|−1
|1
|−1
|−1
|1
|−1
|−1
|−1
|1
|−1
|1
|1
|1
|1
|−1
|−1
|1
|0
|1
|-
!31
|1
|1
|−1
|1
|1
|−1
|1
|1
|1
|1
|−1
|−1
|−1
|1
|−1
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|−1
|1
|−1
|−1
|1
|−1
|−1
|-
!33
|1
|1
|0
|1
|−1
|0
|−1
|1
|0
|−1
|0
|0
|−1
|−1
|0
|1
|1
|0
|−1
|−1
|0
|0
|−1
|0
|1
|−1
|0
|−1
|1
|0
|-
!35
|1
|−1
|1
|1
|0
|−1
|0
|−1
|1
|0
|1
|1
|1
|0
|0
|1
|1
|−1
|−1
|0
|0
|−1
|−1
|−1
|0
|−1
|1
|0
|1
|0
|-
!37
|1
|−1
|1
|1
|−1
|−1
|1
|−1
|1
|1
|1
|1
|−1
|−1
|−1
|1
|−1
|−1
|−1
|−1
|1
|−1
|−1
|−1
|1
|1
|1
|1
|−1
|1
|-
!39
|1
|1
|0
|1
|1
|0
|−1
|1
|0
|1
|1
|0
|0
|−1
|0
|1
|−1
|0
|−1
|1
|0
|1
|−1
|0
|1
|0
|0
|−1
|−1
|0
|-
!41
|1
|1
|−1
|1
|1
|−1
|−1
|1
|1
|1
|−1
|−1
|−1
|−1
|−1
|1
|−1
|1
|−1
|1
|1
|−1
|1
|−1
|1
|−1
|−1
|−1
|−1
|−1
|-
!43
|1
|−1
|−1
|1
|−1
|1
|−1
|−1
|1
|1
|1
|−1
|1
|1
|1
|1
|1
|−1
|−1
|−1
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|−1
|−1
|-
!45
|1
|−1
|0
|1
|0
|0
|−1
|−1
|0
|0
|1
|0
|−1
|1
|0
|1
|−1
|0
|1
|0
|0
|−1
|−1
|0
|0
|1
|0
|−1
|1
|0
|-
!47
|1
|1
|1
|1
|−1
|1
|1
|1
|1
|−1
|−1
|1
|−1
|1
|−1
|1
|1
|1
|−1
|−1
|1
|−1
|−1
|1
|1
|−1
|1
|1
|−1
|−1
|-
!49
|1
|1
|1
|1
|1
|1
|0
|1
|1
|1
|1
|1
|1
|0
|1
|1
|1
|1
|1
|1
|0
|1
|1
|1
|1
|1
|1
|0
|1
|1
|-
!51
|1
|−1
|0
|1
|1
|0
|−1
|−1
|0
|−1
|1
|0
|1
|1
|0
|1
|0
|0
|1
|1
|0
|−1
|1
|0
|1
|−1
|0
|−1
|1
|0
|-
!53
|1
|−1
|−1
|1
|−1
|1
|1
|−1
|1
|1
|1
|−1
|1
|−1
|1
|1
|1
|−1
|−1
|−1
|−1
|−1
|−1
|1
|1
|−1
|−1
|1
|1
|−1
|-
!55
|1
|1
|−1
|1
|0
|−1
|1
|1
|1
|0
|0
|−1
|1
|1
|0
|1
|1
|1
|−1
|0
|−1
|0
|−1
|−1
|0
|1
|−1
|1
|−1
|0
|-
!57
|1
|1
|0
|1
|−1
|0
|1
|1
|0
|−1
|−1
|0
|−1
|1
|0
|1
|−1
|0
|0
|−1
|0
|−1
|−1
|0
|1
|−1
|0
|1
|1
|0
|-
!59
|1
|−1
|1
|1
|1
|−1
|1
|−1
|1
|−1
|−1
|1
|−1
|−1
|1
|1
|1
|−1
|1
|1
|1
|1
|−1
|−1
|1
|1
|1
|1
|1
|−1
|}

== Lastnosti ==
Sledeča dejstva, celo obratni zakoni, so direktne dedukcije iz definicije Jacobijevega simbola in pripadajočih lastnosti Legendrovega simbola.<ref>Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10</ref>

Tacobijev simbol je definiran le, ko je števec celo število in imenovalec pozitivno liho število.

: 1. Če je ''n'' (liho) praštevilo, potem je Jacobijev simbol {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}} enak (in zapisan enako kot) pripadajoči Legendrov simbol.

: 2. Če je {{Brez preloma|''a'' ≡ ''b'' &nbsp;(mod ''n'')}}, potem je <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{če } D(a,n) \ne 1,\\
\pm1 & \text{če } D(a,n) = 1.
\end{cases}
</math>

Če je katerikoli izmed števca ali imenovalca stalen, potem je Jacobijev simbol [[popolnoma multiplikativna funkcija]] v preostalem argumentu:

: 4. <math>\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right),\quad\text{torej } \left(\frac{a^2}{n}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ ali } 0.</math>

: 5. <math>\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right),\quad\text{torej } \left(\frac{a}{n^2}\right) = \left(\frac{a}{n}\right)^2 = 1 \text{ ali } 0.</math>

[[Kvadratni recipročnostni zakon]]: če sta si ''m'' in ''n'' lihi tuji naravni števili, potem je

: 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{če } n \equiv 1 \pmod 4 \text{ ali } m \equiv 1 \pmod 4,\\
-1 & \text{če } n\equiv m \equiv 3 \pmod 4
\end{cases}
</math>

: 7. <math>\left(\frac{-1}{n}\right) = (-1)^\tfrac{n-1}{2} = 
\begin{cases} 
1 & \text{če }n \equiv 1 \pmod 4,\\
-1 & \text{če }n \equiv 3 \pmod 4,
\end{cases}
</math>

in to se da prepisati v

: 8. <math>\left(\frac{2}{n}\right) = (-1)^\tfrac{n^2-1}{8} = 
\begin{cases} 1 & \text{če }n \equiv 1,7 \pmod 8,\\
-1 & \text{če }n \equiv 3,5\pmod 8.
\end{cases}
</math>

: 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{če }n \equiv 1,7 \pmod 8,\\
- \left(\frac{a}{n}\right) & \text{če }n \equiv 3,5\pmod 8.
\end{cases}
</math>

Če združimo lastnosti 4 in 8 dobimo:

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

Kot Legendrov simbol:

* Če je {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}}&nbsp;=&nbsp;−1 potem je ''a'' kvadratni modulo ''n'' brez ostanka.

* Če je ''a'' [[kvadratni ostanek]] modula ''n'' in [[Največji skupni delitelj|D]](''a'',''n'')&nbsp;=&nbsp;1, potem {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}}&nbsp;=&nbsp;1.

A za razliko od Legendrovega simbola:

: Če je {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}}&nbsp;=&nbsp;1, potem je ''a'' lahko ali pa ne kvadratni modulo ''n'' z ostankom.

To se zgodi zato, ker mora za ''a'', ki je kvadratni modulo ''n'' z ostankom, obstajati kvadratni modulo z ostankom za ''vsaki'' praštevilski faktor od ''n''. A Jacobijev simbol je enak enemu od teh, če je, ''a'' enak modulu brez ostanka z natančno dvema izmed praštevilskih faktorjev od ''n''.

Četudi se Jacobijevega simbola ne da unikatno predstaviti s kvadrati in ne-kvadrati, se lahko unikatno opredeli kot znak permutacije po [[Zolotareva lema|Zolotarevi lemi]].

Jacobijev simbol {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}} je [[Dirichletov znak]] k modulom ''n''.

== Izračunavanje Jacobijevega simbola ==
Zgornje formule vodijo v učinkoviti algoritem {{Brez preloma|[[Zapis veliki O|''O'']](log ''a'' log ''b'')}}<ref>Cohen, pp. 29–31</ref> za izračunavanje Jacobijevega simbola, ki je analogen [[Evklidov algoritem|Evklidovemu algoritmu]] za iskanje največjega skupnega delitelja dveh števil (To se ne zdi preveč presenetljivo zaradi pravila 2).

# Zmanjšaj modulo števca na imenovalec z uporabo pravila 2.
# Izrazi katerikoli sodi števec z uporabo pravila 9.
# Če je števec enak 1, nam dajo pravila 3 in 4 rezultat 1. Če pa števec in imenovalec nista tuji si števili, nam pravilo 3 da rezultat 0.
# Če se noben izmed zgornjih primerov ni uresničil, potem sta števec in imenovalec sedaj lihi tuji si naravni števili, kar pomeni, da lahko obrnemo simbol z uporabo pravila 6 in se nato vrnemo na korak 1.

=== Implementacija v jeziku [[Lua (programski jezik)|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>

== Primeri računanja ==
Legendrov simbol {{Veliko|(}}{{Sfrac|''a''|''p''}}{{Veliko|)}} je definiran le za liha praštevila ''p''. Upošteva enaka pravila kot Jacobijev simbol (torej recipročnost in suplementarne formule za {{Veliko|(}}{{Sfrac|−1|''p''}}{{Veliko|)}} in {{Veliko|(}}{{Sfrac|2|''p''}}{{Veliko|)}} ter multiplikativnost števca.)

Problem: Če je 9907 praštevilo, izračunaj {{Veliko|(}}{{Sfrac|1001|9907}}{{Veliko|)}}.

=== Z uporabo Legendrovega simbola ===

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

=== Z uporabo Jacobijevega simbola ===

: <math>\begin{align}
\left(\frac{19}{45}\right) &= 1  &&\text{ in } & 19^\frac{45-1}{2} &\equiv  1\pmod{45}. \\
\left(\frac{ 8}{21}\right) &= -1 &&\text{ toda } &  8^\frac{21-1}{2} &\equiv  1\pmod{21}. \\
\left(\frac{ 5}{21}\right) &= 1  &&\text{ toda } &  5^\frac{21-1}{2} &\equiv 16\pmod{21}.
\end{align}</math>

Razlika med obema izračunoma je v tem, da mora biti Legendrov simbol, ko je uporabljen kot števec, najprej faktoriziran, kasneje šele obrnjen. To spremeni izračun Legendrovega simbola opazno počasnejšega kot Jacobijevega simbola, ker sedaj še ni znan algoritem za polinomsko-časovno faktoriziranje celih števil.<ref>The [[number field sieve]], the fastest known algorithm, requires</ref> Ravno zato je tudi Jacobi vpeljal svoj simbol.

== Praštevilski test ==
Obstaja še ena stvar, v kateri se oba simbola razlikujeta. Če se za modulo sestavljenega števila uporablja [[Eulerjeva kriterijska formula|Eulerjeva kriterijska]] formula, potem je rezultat lahko ali pa ni vrednost Jacobijevega simbola, v resnici lahko celo ni niti −1 niti 1. Na primer

: <math>\begin{align}
\left(\frac{19}{45}\right) &= 1  &&\text{ in } & 19^\frac{45-1}{2} &\equiv  1\pmod{45}. \\
\left(\frac{ 8}{21}\right) &= -1 &&\text{ toda } &  8^\frac{21-1}{2} &\equiv  1\pmod{21}. \\
\left(\frac{ 5}{21}\right) &= 1  &&\text{ toda } &  5^\frac{21-1}{2} &\equiv 16\pmod{21}.
\end{align}</math>

Torej če je znano, ali je število ''n'' praštevilo ali sestavljeno število, lahko izberemo naključno število ''a'', izračunamo Jacobijev simbol {{Veliko|(}}{{Sfrac|''a''|''n''}}{{Veliko|)}} in ga primerjamo z Eulerjevo formulo; če se razlikuje v modulu ''n'', potem je ''n'' sestavljeno število; če pa ima enak ostanek v modulu ''n'' za več različnih vrednosti ''a'', potem pa je ''n'' "verjetno praštevilo".

To je osnova verjetnostnega [[Solovay–Strassen praštevilski test|Solovay–Strassen praštevilskega testa]] in zožitve, kot so [[Baillie-PSW praštevilski test]] in [[Miller–Rabin praštevilski test]].

Kot posredna uporaba, je to možno uporabiti tudi kot zaznavo napake med izvajanjem [[Lucas-Lehmer praštevilski test|Lucas-Lehmer praštevilskega testa]], ki se tudi na sodobnih računalnikih lahko izvaja tudi več tednov za izračunavanje [[Mersennovo število|Mersennovih števil]], ki so višja od <math>\begin{align}2^{82,589,933} - 1\end{align}</math> (največje znano Mersennovo število (decembra 2018). V posebnem primeru, je Jacobijev simbol:

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

To drži tudi za končni ostanek <math>\begin{align}s_{p-2}\end{align}</math> in se torej lahko uporablja kot potrditev verjetne veljavnosti. A če se na trdih komponentah računalnika zgodi napaka, potem obstaja 50% možnost, da bo rezultat postal 0 ali 1, in se ne bo spreminjal s <math>\begin{align}s\end{align}</math> (razen če se zgodi še ena napaka, potem se spremeni nazaj na -1).

== Glej tudi ==

* [[Kroneckerjev simbol]], posplošitev Jacobijevega simbola na vsa cela števila.
* [[simbol ostanka potence]], posplošitev Jacobijevega simbola na ostanke višjih potenc.

== Sklici ==

{{sklici|1}}

== Viri ==

* {{Navedi knjigo|last=Cohen|first=Henri|title=A Course in Computational Algebraic Number Theory|publisher=[[Springer Science+Business Media|Springer]]|location=Berlin|date=1993|isbn=3-540-55640-0}}
* {{Navedi knjigo|last=Ireland|first=Kenneth|last2=Rosen|first2=Michael|title=A Classical Introduction to Modern Number Theory (Second edition)|publisher=[[Springer Science+Business Media|Springer]]|location=New York|date=1990|isbn=0-387-97329-X}}
* {{Navedi knjigo|last=Lemmermeyer|first=Franz|title=Reciprocity Laws: from Euler to Eisenstein|url=https://archive.org/details/reciprocitylawsf0000lemm|publisher=[[Springer Science+Business Media|Springer]]|location=Berlin|date=2000|isbn=3-540-66957-4}}

== Zunanje povezave ==

* [http://math.fau.edu/richman/jacobi.htm Izračunaj Jacobijev simbol] pokaže korake za izvedbo računanja.

[[Kategorija:Modularna aritmetika]]