Символ Якобі

Символ Якобі $\left({\frac {a}{n}}\right)$ — функція в теорії чисел, що узагальнює символ Лежандра для довільних непарних натуральних чисел $n$ :

Якщо $n$ є простим числом, то символ Якобі дорівнює символу Лежандра.
Якщо розклад $n$ на прості множники має вигляд $p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{k}^{c_{k}}$ , то символ Якобі рівний:
$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{c_{1}}\left({\frac {a}{p_{2}}}\right)^{c_{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{c_{k}}$

де в правій частині стоять символи Лежандра.

Символ запровадив в 1837 році Карл Якобі.

Властивості

Якщо

a=b\mod n

, то

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)

\left({\frac {a}{n}}\right)=0

a

і

n

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)

\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)

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

\left({\frac {-1}{n}}\right)=1

якщо

n=1\mod 4

\left({\frac {-1}{n}}\right)=-1

якщо

n=3\mod 4

\left({\frac {2}{n}}\right)=1

якщо

n=1\mod 8

або

n=7\mod 8

\left({\frac {2}{n}}\right)=-1

якщо

n=3\mod 8

або

n=5\mod 8

\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}

\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 {4}{29}}\right)\left({\frac {2}{29}}\right)=-1.

ЯКОБІ(a, n)^[1]^:73

Вхід: непарне ціле число $n\geq 3$ і ціле $a,0\leq a<n.$

Вихід: символ Якобі $\left({\frac {a}{n}}\right)$ (відповідно символ Лежандра, якщо $n$ просте).

Якщо $a=0,$ тоді повернути(0).
Якщо $a=1,$ тоді повернути(1).
Записати $a=2^{e}a_{1},$ де $a_{1}$ непарне.
Якщо $e$ парне, тоді покласти $s\gets 1.$ Інакше, покласти $s\gets 1$ якщо $n\equiv \pm 1{\pmod {8}}$ або покласти $s\gets -1,$ якщо $n\equiv \pm 3{\pmod {8}}.$
Якщо $n\equiv 3{\pmod {4}}$ і $a_{1}\equiv 3{\pmod {4}},$ тоді покласти $s\gets -s.$
Покласти $n_{1}\gets n\mod a_{1}.$
Якщо $a_{1}=1$ тоді повернути(s); інакше повернути( $s\times$ ЯКОБІ $(n_{1},a_{1})$ ).