Русская Википедия:Символ Кронекера — Якоби
Шаблон:Distinguish Шаблон:Другие значения термина Шаблон:Другие значения термина Символ Кронекера — Якоби — функция, используемая в теории чисел. Иногда называют символом Лежандра — Якоби — Кронекера или просто символом Кронекера.
Символ Кронекера — Якоби является обобщением символов Лежандра и Якоби. Символ Лежандра определён только для простых чисел, символ Якоби — для натуральных нечётных чисел, а символ Кронекера — Якоби расширяет это понятие на все целые числа.
Определение
Символ Кронекера — Якоби <math>\left(\frac{a}{b}\right)</math> определяется следующим образом:
- если <math>b</math> — простое нечётное число, то символ Кронекера — Якоби совпадает с символом Лежандра;
- если <math>b=0</math>, то <math>\left(\frac{a}{0}\right)=
\begin{cases}
1, & \text{if}\ a=\pm 1, \\
0, & \text{if}\ a\neq\pm 1;
\end{cases}</math>
- если <math>b=2</math>, то <math>\left(\frac{a}{2}\right)=
\begin{cases}
0, & \text{if}\ a\equiv 0\pmod{2}, \\
(-1)^{\frac{a^2-1}{8}}, & \text{if}\ a\equiv 1\pmod{2}; \end{cases}</math>
- если <math>b=-1</math>, то <math>\left(\frac{a}{-1}\right)=
\begin{cases} -1, & \text{if}\ a < 0, \\ 1, & \text{if}\ a\geqslant 0; \end{cases} </math>
- если <math>b=\delta\cdot p_1\cdot\ldots\cdot p_n</math>, где <math>\delta=\pm 1</math>, <math>p_1,\;\ldots,\;p_n</math> — простые (не обязательно различные), то
- <math>\left(\frac{a}{b}\right)=\left(\frac{a}{\delta}\right)\cdot\left(\frac{a}{p_1}\right)\cdots\left(\frac{a}{p_n}\right),</math>
где <math>\left(\frac{a}{p_i}\right)</math> определены выше.
Свойства
- <math>\left(\frac{a}{b}\right)=0</math> тогда и только тогда, когда <math>(a,\;b)\neq 1</math> (<math>a</math> и <math>b</math> не взаимно просты).
- Мультипликативность: <math>\left(\frac{ab}{c}\right)=\left(\frac{a}{c}\right)\left(\frac{b}{c}\right)</math>.
- В частности, <math>\left(\frac{a^2b}{c}\right)=\left(\frac{b}{c}\right)</math>.
- Периодичность по переменной <math>a</math>: если <math>b>0</math>, то
- Периодичность по переменной <math>b</math>: если <math>a\neq 0</math>, то
- при <math>a\equiv 0;\;1\pmod{4}</math> период равен <math>|a|</math>, то есть <math>\left(\frac{a}{b+\left|a\right |}\right)=\left(\frac{a}{b}\right)</math>;
- при <math>a\equiv 2;\;3\pmod{4}</math> период равен <math>4|a|</math>, то есть <math>\left(\frac{a}{b+4\left|a\right |}\right)=\left(\frac{a}{b}\right)</math>.
- Если <math>b</math> — нечётное натуральное число, то выполнены свойства символа Якоби:
- <math>\left(\frac{1}{b}\right)=1;</math>
- <math>\left(\frac{-1}{b}\right)=(-1)^{\frac{b-1}{2}};</math>
- <math>\left(\frac{2}{b}\right)=(-1)^{\frac{b^2-1}{8}}.</math>
- Аналог квадратичного закона взаимности: если <math>A,\;B</math> — нечётные натуральные числа, то <math>\left(\frac{A}{B}\right)\left(\frac{B}{A}\right)=(-1)^{\frac{A-1}{2}\cdot\frac{B-1}{2}}</math>.
Связь с перестановками
Пусть <math>n</math> — натуральное число, а <math>a</math> взаимно просто с <math>n</math>. Отображение <math>m_a: x\to ax\mod n</math>, действующее на всём <math>\mathbb{Z}/n\mathbb{Z}</math> определяет перестановку <math>\pi_a\in S_n</math>, чётность которой равна символу Якоби:
- <math>\sigma(\pi_a)=\left(\frac{a}{n}\right).</math>
Алгоритм вычисления
1. (Случай b=0)
Если <math>b=0</math> то
Если <math>|a|=1</math>, то выход из алгоритма с ответом 1
Если <math>|a|\neq1</math>, то выход из алгоритма с ответом 0
Конец Если
2. (Чётность b)
Если a и b оба чётные, то выйти из алгоритма и вернуть 0
<math>v=0</math>
Цикл Пока b – чётное
<math>v:=v+1; b:=b/2</math>
Конец цикла
Если v – чётное, то k=1, иначе иначе <math>k=(-1)^{\frac{a^2-1}{8}}</math>
Если <math>b<0</math>, то
<math>b:=-b</math>
Если <math>a<0</math>, то <math>k:=-k</math>
Конец Если
3. (Выход из алгоритма?)
Если <math>a=0</math>, то
Если <math>b>1</math>, то выход из алгоритма с ответом 0
Если <math>b=1</math>, то выход из алгоритма с ответом k
Конец Если
<math>v:=0</math>
Цикл Пока a – чётное
<math>v:=v+1; a:=a/2</math>
Конец цикла
Если v – нечётное, то <math>k:=(-1)^{\frac{b^2-1}{8}}k</math>
4. (Применение квадратичного закона взаимности)
<math>k:=k(-1) ^{\frac{(a-1)(b-1)}{4}}</math>
<math>r:=|a|</math>
<math>a:=b\mod{r}</math> (наименьший положительный вычет)
<math>b:=r</math>
Идти на шаг 3
Замечание: для подсчёта <math>(-1)^{\frac{a^2-1}{8}}</math> не нужно вычислять показатель степени, достаточно знать остаток от деления <math>a</math> на 8. Это увеличивает скорость работы алгоритма.
Список литературы
