Символ Кронекера — Якоби


Символ Кронекера — Якоби — функция, используемая в теории чисел. Иногда называют символом Лежандра — Якоби — Кронекера или просто символом Кронекера.

Символ Кронекера — Якоби является обобщением символов Лежандра и Якоби. Символ Лежандра определён только для простых чисел, символ Якоби — для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.

Определение

Символ Кронекера — Якоби ( a b ) {displaystyle left({frac {a}{b}} ight)} определяется следующим образом:

  • если b {displaystyle b} — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
  • если b = 0 {displaystyle b=0} , то ( a 0 ) = { 1 , if   a = ± 1 , 0 , if   a ≠ ± 1 ; {displaystyle left({frac {a}{0}} ight)={egin{cases}1,&{ ext{if}} a=pm 1,,&{ ext{if}} a eq pm 1;end{cases}}}
  • если b = 2 {displaystyle b=2} , то ( a 2 ) = { 0 , if   a ≡ 0 ( mod 2 ) , ( − 1 ) a 2 − 1 8 , if   a ≡ 1 ( mod 2 ) ; {displaystyle left({frac {a}{2}} ight)={egin{cases}0,&{ ext{if}} aequiv 0{pmod {2}},(-1)^{frac {a^{2}-1}{8}},&{ ext{if}} aequiv 1{pmod {2}};end{cases}}}
  • если b = − 1 {displaystyle b=-1} , то ( a − 1 ) = { − 1 , if   a < 0 , 1 , if   a ⩾ 0 ; {displaystyle left({frac {a}{-1}} ight)={egin{cases}-1,&{ ext{if}} a<0,1,&{ ext{if}} ageqslant 0;end{cases}}}
  • если b = δ ⋅ p 1 ⋅ … ⋅ p n {displaystyle b=delta cdot p_{1}cdot ldots cdot p_{n}} , где δ = ± 1 {displaystyle delta =pm 1} , p 1 , … , p n {displaystyle p_{1},;ldots ,;p_{n}} — простые (не обязательно различные), то
( a b ) = ( a δ ) ⋅ ( a p 1 ) ⋯ ( a p n ) , {displaystyle left({frac {a}{b}} ight)=left({frac {a}{delta }} ight)cdot left({frac {a}{p_{1}}} ight)cdots left({frac {a}{p_{n}}} ight),}

где ( a p i ) {displaystyle left({frac {a}{p_{i}}} ight)} определены выше.

Свойства

  • ( a b ) = 0 {displaystyle left({frac {a}{b}} ight)=0} тогда и только тогда, когда ( a , b ) ≠ 1 {displaystyle (a,;b) eq 1} ( a {displaystyle a} и b {displaystyle b} не взаимно просты).
  • Мультипликативность: ( a b c ) = ( a c ) ( b c ) {displaystyle left({frac {ab}{c}} ight)=left({frac {a}{c}} ight)left({frac {b}{c}} ight)} .
    • В частности, ( a 2 b c ) = ( b c ) {displaystyle left({frac {a^{2}b}{c}} ight)=left({frac {b}{c}} ight)} .
  • Периодичность по переменной a {displaystyle a} : если b > 0 {displaystyle b>0} , то
    • при b ≢ 2 ( mod 4 ) {displaystyle b ot equiv 2{pmod {4}}} период равен b {displaystyle b} , то есть ( a + b b ) = ( a b ) {displaystyle left({frac {a+b}{b}} ight)=left({frac {a}{b}} ight)} ;
    • при b ≡ 2 ( mod 4 ) {displaystyle bequiv 2{pmod {4}}} период равен 4 b {displaystyle 4b} , то есть ( a + 4 b b ) = ( a b ) {displaystyle left({frac {a+4b}{b}} ight)=left({frac {a}{b}} ight)} .
  • Периодичность по переменной b {displaystyle b} : если a ≠ 0 {displaystyle a eq 0} , то
    • при a ≡ 0 ; 1 ( mod 4 ) {displaystyle aequiv 0;;1{pmod {4}}} период равен | a | {displaystyle |a|} , то есть ( a b + | a | ) = ( a b ) {displaystyle left({frac {a}{b+left|a ight|}} ight)=left({frac {a}{b}} ight)} ;
    • при a ≡ 2 ; 3 ( mod 4 ) {displaystyle aequiv 2;;3{pmod {4}}} период равен 4 | a | {displaystyle 4|a|} , то есть ( a b + 4 | a | ) = ( a b ) {displaystyle left({frac {a}{b+4left|a ight|}} ight)=left({frac {a}{b}} ight)} .
  • Если b {displaystyle b} — нечётное натуральное число, то выполнены свойства символа Якоби:
    • ( 1 b ) = 1 ; {displaystyle left({frac {1}{b}} ight)=1;}
    • ( − 1 b ) = ( − 1 ) b − 1 2 ; {displaystyle left({frac {-1}{b}} ight)=(-1)^{frac {b-1}{2}};}
    • ( 2 b ) = ( − 1 ) b 2 − 1 8 . {displaystyle left({frac {2}{b}} ight)=(-1)^{frac {b^{2}-1}{8}}.}
  • Аналог квадратичного закона взаимности: если A , B {displaystyle A,;B} — нечётные натуральные числа, то ( A B ) ( B A ) = ( − 1 ) A − 1 2 ⋅ B − 1 2 {displaystyle left({frac {A}{B}} ight)left({frac {B}{A}} ight)=(-1)^{{frac {A-1}{2}}cdot {frac {B-1}{2}}}} .

Связь с перестановками

Пусть n {displaystyle n} — натуральное число, а a {displaystyle a} взаимно просто с n {displaystyle n} . Отображение m a : x → a x mod n {displaystyle m_{a}:x o axmod n} , действующее на всём Z / n Z {displaystyle mathbb {Z} /nmathbb {Z} } определяет перестановку π a ∈ S n {displaystyle pi _{a}in S_{n}} , чётность которой равна символу Якоби:

σ ( π a ) = ( a n ) . {displaystyle sigma (pi _{a})=left({frac {a}{n}} ight).}

Алгоритм вычисления

1. (Случай b=0) Если b = 0 {displaystyle b=0} то Если | a | = 1 {displaystyle |a|=1} , то выход из алгоритма с ответом 1 Если | a | ≠ 1 {displaystyle |a| eq 1} , то выход из алгоритма с ответом 0 Конец Если 2. (Чётность b) Если a и b оба чётные, то выйти из алгоритма и вернуть 0 v = 0 {displaystyle v=0} Цикл Пока b – чётное v := v + 1 ; b := b / 2 {displaystyle v:=v+1;b:=b/2} Конец цикла Если v – чётное, то k=1, иначе иначе k = ( − 1 ) a 2 − 1 8 {displaystyle k=(-1)^{frac {a^{2}-1}{8}}} Если b < 0 {displaystyle b<0} , то b := − b {displaystyle b:=-b} Если a < 0 {displaystyle a<0} , то k := − k {displaystyle k:=-k} Конец Если 3. (Выход из алгоритма?) Если a = 0 {displaystyle a=0} , то Если b > 1 {displaystyle b>1} , то выход из алгоритма с ответом 0 Если b = 1 {displaystyle b=1} , то выход из алгоритма с ответом k Конец Если v := 0 {displaystyle v:=0} Цикл Пока a – чётное v := v + 1 ; a := a / 2 {displaystyle v:=v+1;a:=a/2} Конец цикла Если v – нечётное, то k := ( − 1 ) b 2 − 1 8 k {displaystyle k:=(-1)^{frac {b^{2}-1}{8}}k} 4. (Применение квадратичного закона взаимности) k := k ( − 1 ) ( a − 1 ) ( b − 1 ) 4 {displaystyle k:=k(-1)^{frac {(a-1)(b-1)}{4}}} r := | a | {displaystyle r:=|a|} a := b mod r {displaystyle a:=bmod {r}} (наименьший положительный вычет) b := r {displaystyle b:=r} Идти на шаг 3

Замечание: для подсчёта ( − 1 ) a 2 − 1 8 {displaystyle (-1)^{frac {a^{2}-1}{8}}} не нужно вычислять показатель степени, достаточно знать остаток от деления a {displaystyle a} на 8. Это увеличивает скорость работы алгоритма.

Список литературы

  • Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952. — С. 180. — ISBN 5-93972-252-0.
  • Н. Cohen. A course in computational algebraic number theory. — Springer, 1996. — ISBN 3-540-55640-0.

Имя:*
E-Mail:
Комментарий: