Символ Якобі

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

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

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

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

Властивості

Якщо

a = b mod n

, то

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

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

a

і

n

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

(\frac{a}{m n}) = (\frac{a}{m}) (\frac{a}{n})

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

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

якщо

n = 1 mod 4

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

якщо

n = 3 mod 4

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

якщо

n = 1 mod 8

або

n = 7 mod 8

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

якщо

n = 3 mod 8

або

n = 5 mod 8

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

(\frac{1001}{9907}) = (\frac{9907}{1001}) = (\frac{898}{1001}) = (\frac{2}{1001}) (\frac{449}{1001}) = (\frac{449}{1001})

= (\frac{1001}{449}) = (\frac{103}{449}) = (\frac{449}{103}) = (\frac{37}{103}) = (\frac{103}{37})

= (\frac{29}{37}) = (\frac{37}{29}) = (\frac{8}{29}) = (\frac{4}{29}) (\frac{2}{29}) = - 1 .

ЯКОБІ(a, n)^[1]Шаблон:Rp

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

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

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