Символ Лежандра

редактировать

Символ Лежандра (a / p). для различных a (вверху) и p (слева).
ap	0	1	2	3	4	5	6	7	8	9	10
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
11	−0	−1	−1	1	−1	1	−1	−1	−1	−1	−1
Только 0 ≤ a < p are shown, since due to the first property below any other a can be reduced modulo p. Квадратичные вычеты выделены желтым цветом и точно соответствуют значениям 0 и 1.

В теории чисел символ Лежандра является мультипликативная функция со значениями 1, -1, 0, которая представляет собой квадратичный символ по модулю нечетного простого числа p: ее значение при (ненулевом) квадратичном остатке по модулю p равно 1, а при неквадратичном вычете (невычете) равно -1. Его нулевое значение равно 0.

Символ Лежандра был введен Адрианом-Мари Лежандром в 1798 году в ходе его попыток доказать закон квадратичной взаимности. Обобщения символа включают в себя символ Якоби и символы Дирихле более высокого порядка. Удобство обозначений символа Лежандра вдохновило на введение нескольких других «символов», используемых в теории алгебраических чисел, таких как символ Гильберта и символ Артина.

Содержание

1 Определение
2 Таблица значений
3 Свойства символа Лежандра
4 Символ Лежандра и квадратичная взаимность
5 Связанные функции
6 Расчетный пример
7 Примечания
8 Ссылки
9 Внешние ссылки

Определение

Пусть $p {\ displaystyle p}$ $p$ будет нечетным простым числом. Целое число $a {\ displaystyle a}$ $a$ является квадратичным остатком по модулю $p {\ displaystyle p}$ $p$ , если оно конгруэнтно в полный квадрат по модулю $p {\ displaystyle p}$ $p$ и является квадратичным невычетом по модулю $p {\ displaystyle p}$ $p$ в противном случае. символ Лежандра является функцией $a {\ displaystyle a}$ $a$ и $p {\ displaystyle p}$ $p$ , определенного как

( ap) = {1, если a - квадратичный вычет по модулю p, и a ≢ 0 (mod p), - 1, если a - неквадратичный вычет по модулю p, 0, если a ≡ 0 (mod p). {\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} 1 {\ text {if}} a {\ text {- квадратичный остаток по модулю}} p {\ text {and}} a \ not \ Equiv 0 {\ pmod {p}}, \\ - 1 {\ text {if}} a {\ text {неквадратичный вычет по модулю}} p, \\ 0 {\ text {if}} a \ Equiv 0 {\ pmod {p}}. \ end {ases}}}

{\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} 1 {\ text {if}} a {\ text {- квадратичный остаток modulo}} p {\ text {and}} a \ not \ Equiv 0 {\ pmod {p}}, \\ - 1 {\ text {if}} a {\ text {неквадратичный вычет по модулю}} p, \\ 0 {\ text {if}} a \ Equiv 0 {\ pmod {p}}. \ end {cases}}}

Первоначальное определение Лежандра использовалось с помощью явной формулы

(ap) ≡ ap - 1 2 (mod p) и (ap) ∈ {- 1, 0, 1}. {\ displaystyle \ left ({\ frac {a} {p}} \ right) \ Equiv a ^ {\ frac {p-1} {2}} {\ pmod {p}} \ quad {\ text {и} } \ quad \ left ({\ frac {a} {p}} \ right) \ in \ {- 1,0,1 \}.}

{\ displaystyle \ left ({\ frac {a} {p}} \ right) \ Equiv a ^ {\ frac {p-1} {2}} {\ pmod {p}} \ quad {\ текст {и}} \ quad \ left ({\ frac {a} {p}} \ right) \ in \ {- 1,0,1 \}.}

По критерию Эйлера, который был обнаружен ранее и были известны Лежандру, эти два определения эквивалентны. Таким образом, вклад Лежандра заключался во введении удобных обозначений, которые фиксируют квадратичную вычетность по модулю p. Для сравнения, Gauss использовал обозначение aRp, aNp в зависимости от того, является ли a остатком или не остатком по модулю p. Для удобства печати символ Лежандра иногда пишется как (a | p) или (a / p). Последовательность (a | p) для a, равного 0, 1, 2,... является периодической с периодом p и иногда называется последовательностью Лежандра с {0,1, −1} значения иногда заменяются на {1,0,1} или {0,1,0}. Каждая строка в следующей таблице демонстрирует периодичность, как описано.

Таблица значений

Ниже представлена таблица значений символа Лежандра $(ap) {\ displaystyle \ left ({\ frac {a} {p}} \ right) }$ $\ left ({\ frac {a} {p}} \ right)$ с p ≤ 127, a ≤ 30, p нечетным простым числом.

ap	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
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
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
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
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
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
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
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
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
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
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
61	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
67	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
71	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
73	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
79	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
83	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
89	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
97	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
101	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
103	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
107	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
109	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
113	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
127	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

Свойства символа Лежандра

Существует ряд полезных свойств символа Лежандра, которые вместе с законом квадратичной взаимности, можно использовать для его эффективного вычисления.

Символ Лежандра показывает четность ненулевого целого по модулю p. То есть для генератора $g ∈ F p ∗ {\ displaystyle g \ in \ mathbb {F} _ {p} ^ {*}}$ ${\ displaystyle g \ in \ mathbb {F} _ {p} ^ {*}}$ , если $x = gr {\ displaystyle x = g ^ {r}}$ ${\ displaystyle x = g ^ {r}}$ , тогда $x {\ displaystyle x}$ $x$ является квадратичным остатком тогда и только тогда, когда $r {\ displaystyle r}$ $r$ - четное. Это также показывает, что половина ненулевых элементов в $F p ∗ {\ displaystyle \ mathbb {F} _ {p} ^ {*}}$ ${\ mathbb {F}} _ {p} ^ {*}$ являются квадратичными вычетами.
Если $p ≡ 3 mod 4 {\ displaystyle p \ Equiv 3 {\ text {mod}} 4}$ ${\ displaystyle p \ Equiv 3 {\ текст {мод}} 4}$ , то тот факт, что
$p + 1 4 + p + 1 4 = ( п - 1) + 2 2 {\ displaystyle {\ frac {p + 1} {4}} + {\ frac {p + 1} {4}} = {\ frac {(p-1) +2} {2 }}}$ ${\ displaystyle {\ frac {p + 1} { 4}} + {\ frac {p + 1} {4}} = {\ frac {(p-1) +2} {2}}}$ дает нам, что $a = x (p + 1) / 4 {\ displaystyle a = x ^ {(p + 1) / 4}}$ ${\ displaystyle a = x ^ {(p + 1) / 4 }}$ - это квадратный корень из квадратичного остатка $x {\ displaystyle x}$ $x$ .
Символ Лежандра периодичен в своем первом (или верхнем) аргументе: если a ≡ b (mod p), то
$(ap) = ( п.н.). {\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right).}$ $\ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right).$
Символ Лежандра представляет собой полностью мультипликативная функция своего верхнего аргумента:
$(abp) = (ap) (bp). {\ displaystyle \ left ({\ frac {ab} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) \ left ({\ frac {b} {p}} \ справа).}$ $\ left ({\ frac {ab} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) \ left ({\ frac { b} {p}} \ right).$
В частности, произведение двух чисел, которые являются квадратичными остатками или квадратичными невычетами по модулю p, является остатком, тогда как произведение остатка с неостаточным остатком является невычетом. Особым случаем является символ Лежандра квадрата:
$(x 2 p) = {1, если p ∤ x 0, если p ∣ x. {\ displaystyle \ left ({\ frac {x ^ {2}} {p}} \ right) = {\ begin {cases} 1 {\ t_dv {if}} p \ nmid x \\ 0 {\ t_dv {if }} p \ mid x. \ end {cases}}}$ ${\ displaystyle \ слева ({\ f rac {x ^ {2}} {p}} \ right) = {\ begin {cases} 1 {\ t_dv {if}} p \ nmid x \\ 0 {\ t_dv {if}} p \ mid x. \ конец {case}}}$
Если рассматривать как функцию от a, символ Лежандра $(ap) {\ displaystyle \ left ({\ frac {a} {p}} \ right)}$ ${\ displaystyle \ left ({\ frac {a} { p}} \ right)}$ - единственный квадратичный (или порядок 2) символ Дирихле по модулю p.
Первое дополнение к закону квадратичной взаимности:
$( - 1 p) = (- 1) p - 1 2 = {1, если p ≡ 1 (mod 4) - 1, если p ≡ 3 (mod 4). {\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 {\ t_dv { if}} p \ Equiv 1 {\ pmod {4}} \\ - 1 {\ t_dv {if}} p \ Equiv 3 {\ pmod {4}}. \ end {ases}}}$ ${\ displaystyle \ left ({\ frac {-1} {p}} \ right) = ( -1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 {\ t_dv {if}} p \ Equiv 1 {\ pmod {4}} \\ - 1 {\ mb бык {если}} п \ экв 3 {\ pmod {4}}. \ end {cases}}}$
Второе дополнение к закону квадратичной взаимности:
$(2 p) = (- 1) p 2 - 1 8 = {1, если p ≡ 1 или 7 (mod 8) - 1, если p 3 или 5 (mod 8). {\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ tfrac {p ^ {2} -1} {8}} = {\ begin {cases} 1 { \ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 7 {\ pmod {8}} \\ - 1 {\ t_dv {if}} p \ Equiv 3 {\ t_dv {or}} 5 {\ pmod {8}}. \ end {cases}}}$ ${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ tfrac {p ^ {2} -1} {8}} = {\ begin {cases} 1 {\ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 7 {\ pmod {8}} \\ - 1 {\ t_dv {if}} p \ Equiv 3 {\ t_dv {или}} 5 {\ pmod {8}}. \ end {cases}}}$
Специальные формулы для символа Лежандра (ap) {\ displaystyle \ left ({\ frac {a} {p}} \ right)}для малых значений a:
- Для нечетного простого числа p ≠ 3,
  $(3 p) = (- 1) ⌊ p + 1 6 ⌋ = {1, если p ≡ 1 или 11 (mod 12) - 1, если p 5 или 7 (mod 12). {\ displaystyle \ left ({\ frac {3} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {p + 1} {6}} {\ big \ rfloor} } = {\ begin {cases} 1 {\ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 11 {\ pmod {12}} \\ - 1 {\ t_dv {if}} p \ Equiv 5 {\ t_dv {или}} 7 {\ pmod {12}}. \ end {ases}}}$ ${\ displaystyle \ left ({\ frac {3} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {p + 1} {6}} {\ big \ rfloor}} = {\ begin {cases} 1 {\ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 11 {\ pmod {12}} \\ - 1 {\ t_dv {if}} p \ Equiv 5 {\ t_dv {or}} 7 {\ pmod {12}}. \ End {cases}}}$
- Для нечетного простого числа p 5,
  $(5 p) = (- 1) ⌊ 2 p + 2 5 ⌋ = {1, если p ≡ 1 или 4 (mod 5) - 1, если p ≡ 2 или 3 (mod 5). {\ displaystyle \ left ({\ frac {5} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {2p + 2} {5}} {\ big \ rfloor} } = {\ begin {case} 1 {\ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 4 {\ pmod {5}} \\ - 1 {\ t_dv {if}} p \ Equiv 2 {\ t_dv {или}} 3 {\ pmod {5}}. \ end {cases}}}$ ${ \ displaystyle \ left ({\ frac {5} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {2p + 2} {5}} {\ big \ rfloor}} = {\ begin {case} 1 {\ t_dv {if}} p \ Equiv 1 {\ t_dv {or}} 4 {\ pmod {5}} \\ - 1 {\ t_dv {if}} p \ Equiv 2 { \ t_dv {или}} 3 {\ pmod {5}}. \ end {cases}}}$
Числа Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… определяются повторением F 1 = F 2 = 1, F n + 1 = F n + F n-1. Если p - простое число, то
$F p - (p 5) ≡ 0 (mod p), F p ≡ (p 5) (mod p). {\ Displaystyle F_ {p- \ left ({\ frac {p} {5}} \ right)} \ Equiv 0 {\ pmod {p}}, \ qquad F_ {p} \ Equiv \ left ({\ frac { p} {5}} \ right) {\ pmod {p}}.}$ $F_ {p- \ left ({\ frac {p} {5}} \ right)} \ Equiv 0 {\ pmod {p}}, \ qquad F_ {p} \ Equiv \ left ({\ frac {p} {5}} \ right) {\ pmod {p}}.$

Например,

(2 5) = - 1, F 3 = 2, F 2 = 1, (3 5) = - 1, F 4 = 3, F 3 = 2, (5 5) = 0, F 5 = 5, (7 5) = - 1, F 8 = 21, F 7 = 13, (11 5) = 1, F 10 = 55, F 11 = 89. {\ displaystyle {\ begin {align} \ left ({\ tfrac {2} {5}} \ right) = - 1, F_ {3} = 2, F_ { 2} = 1, \\\ left ({\ tfrac {3} {5}} \ right) = - 1, F_ {4} = 3, F_ {3} = 2, \\\ left ( {\ tfrac {5} {5}} \ right) = 0, F_ {5} = 5, \\\ left ({\ tfrac {7} {5}} \ right) = - 1, F_ {8} = 21, F_ {7} = 13, \\\ left ({\ tfrac {11} {5}} \ right) = 1, F_ {10} = 55, F_ {11} = 89. \ End {align}}}

{\ displaystyle {\ begin {align} \ left ({\ tfrac {2} {5}} \ right) = - 1, F_ {3} = 2, F_ {2} = 1, \\\ left ({\ tfrac {3} {5}} \ right) = - 1, F_ {4} = 3, F_ {3} = 2, \\\ left ({\ tfrac {5} {5}} \ right) = 0, F_ {5} = 5, \\ \ left ({\ tfrac {7} {5}} \ right) = - 1, F_ {8} = 21, F_ {7} = 13, \\\ left ({\ tfrac {11} {5 }} \ right) = 1, F_ {10} = 55, F_ {11} = 89. \ end {align}}}

Этот результат исходит из теории последовательностей Люка, которые используются в тестировании на простоту. См. Простое число Стена – Солнце – Солнце.

Символ Лежандра и квадратичная взаимность

Пусть p и q - различные нечетные простые числа. Используя символ Лежандра, можно кратко сформулировать закон квадратичной взаимности :

(q p) (p q) = (- 1) p - 1 2 ⋅ q - 1 2. {\ displaystyle \ left ({\ frac {q} {p}} \ right) \ left ({\ frac {p} {q}} \ right) = (- 1) ^ {{\ tfrac {p-1} {2}} \ cdot {\ tfrac {q-1} {2}}}.}

{\ displaystyle \ left ({\ frac {q} {p}} \ right) \ left ({\ frac {p} {q}} \ right) = (- 1) ^ {{\ tfrac {p-1} {2}} \ cdot {\ tfrac {q-1} {2}}}. }

Многие доказательства квадратичной взаимности основаны на формуле Лежандра

(ap) ≡ ap - 1 2 (мод. P). {\ displaystyle \ left ({\ frac {a} {p}} \ right) \ Equiv a ^ {\ tfrac {p-1} {2}} {\ pmod {p}}.}

\ left ({\ frac {a} {p}} \ right) \ Equiv a ^ {\ tfrac {p-1} {2}} {\ pmod {p}}.

Кроме того, Несколько альтернативных выражений для символа Лежандра были придуманы, чтобы произвести различные доказательства квадратичного закона взаимности.

Гаусс ввел квадратичную сумму Гаусса и использовал формулу

∑ k = 0 p - 1 ζ ak 2 = (ap) ∑ k = 0 p - 1 ζ k 2, ζ = e 2 π ip {\ displaystyle \ sum _ {k = 0} ^ {p-1} \ zeta ^ {ak ^ {2}} = \ left ({\ frac {a} {p}} \ right) \ sum _ {k = 0} ^ {p-1} \ zeta ^ {k ^ {2}}, \ qquad \ zeta = e ^ {\ frac {2 \ pi i} {p}}}

\ sum _ {k = 0} ^ {p-1} \ zeta ^ {ak ^ {2}} = \ left ({\ frac {a} {p}} \ right) \ sum _ {k = 0} ^ {p-1} \ zeta ^ {k ^ {2}}, \ qquad \ zeta = e ^ {\ frac {2 \ pi i} {p}}

в четвертом и шестое доказательство квадратичной взаимности.

Доказательство Кронекера сначала устанавливает, что

(pq) = sgn ⁡ (∏ i = 1 q - 1 2 ∏ k = 1 p - 1 2 (kp - iq)). {\ displaystyle \ left ({\ frac {p} {q}} \ right) = \ operatorname {sgn} \ left (\ prod _ {i = 1} ^ {\ frac {q-1} {2}} \ prod _ {k = 1} ^ {\ frac {p-1} {2}} \ left ({\ frac {k} {p}} - {\ frac {i} {q}} \ right) \ right).}

\ l eft ({\ frac {p} {q}} \ right) = \ operatorname {sgn} \ left (\ prod _ {i = 1} ^ {\ frac {q-1} {2}} \ prod _ {k = 1} ^ {\ frac {p-1} {2}} \ left ({\ frac {k} {p}} - {\ frac {i} {q}} \ right) \ right).

Поменяв местами p и q, он получает соотношение между (p / q) и (q / p).

Одно из доказательств Эйзенштейна начинается с того, что показывает, что

(qp) = ∏ n = 1 p - 1 2 sin ⁡ (2 π qnp) sin ⁡ (2 π np). {\ displaystyle \ left ({\ frac {q} {p}} \ right) = \ prod _ {n = 1} ^ {\ frac {p-1} {2}} {\ frac {\ sin \ left ( {\ frac {2 \ pi qn} {p}} \ right)} {\ sin \ left ({\ frac {2 \ pi n} {p}} \ right)}}.}

\ left ({\ frac {q} {p}} \ right) = \ prod _ {n = 1} ^ {\ frac {p-1} {2}} {\ frac {\ sin \ left ({\ frac {2 \ pi qn} {p}} \ right)} {\ sin \ left ({\ frac {2 \ pi n} {p}} \ right)}}.

Использование определенного эллиптические функции вместо синусоидальной функции Эйзенштейну удалось доказать кубическую и четвертую взаимность.

Связанные функции

Символ Якоби (a / n) является обобщением символа Лежандра, который допускает составной второй (нижний) аргумент n, хотя n все равно должно быть нечетным и положительным. Это обобщение обеспечивает эффективный способ вычисления всех символов Лежандра без факторизации.
Еще одним расширением является символ Кронекера, в котором нижний аргумент может быть любым целым числом.
символ остатка степени (a / n) n обобщает символ Лежандра на более высокую степень n. Символ Лежандра представляет собой символ степенного остатка для n = 2.

Вычислительный пример

Вышеуказанные свойства, включая закон квадратичной взаимности, можно использовать для оценки любого символа Лежандра. Например:

(12345 331) = (3 331) (5 331) (823 331) = (3 331) (5 331) (161 331) = (3 331) (5 331) (7 331) ( 23 331) = (- 1) (331 3) (331 5) (- 1) (331 7) (- 1) (331 23) = - (1 3) (1 5) (2 7) (9 23) = - (1 3) (1 5) (2 7) (3 2 23) = - (1) (1) (1) (1) = - 1. {\ displaystyle {\ begin {align} \ left ({ \ frac {12345} {331}} \ right) = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({ \ frac {823} {331}} \ right) \\ = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({\ frac {161} {331}} \ right) \\ = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({\ frac {7} {331}} \ right) \ left ({\ frac {23} {331}} \ right) \\ = (- 1) \ left ({\ frac {331} { 3}} \ right) \ left ({\ frac {331} {5}} \ right) (- 1) \ left ({\ frac {331} {7}} \ right) (- 1) \ left ({ \ frac {331} {23}} \ right) \\ = - \ left ({\ frac {1} {3}} \ right) \ left ({\ frac {1} {5}} \ right) \ left ({\ frac {2} {7}} \ right) \ left ({\ frac {9} {23}} \ right) \\ = - \ left ({\ frac {1} {3}} \ вправо) \ влево ({\ frac {1} {5}} \ right) \ lef t ({\ frac {2} {7}} \ right) \ left ({\ frac {3 ^ {2}} {23}} \ right) \\ = - (1) (1) (1) ( 1) \\ = - 1. \ end {align}}}

{ \ begin {align} \ left ({\ frac {12345} {331}} \ right) = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({\ frac {823} {331}} \ right) \\ = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({\ frac {161} {331}} \ right) \ \ = \ left ({\ frac {3} {331}} \ right) \ left ({\ frac {5} {331}} \ right) \ left ({\ frac {7} {331}} \ right) \ left ({\ frac {23} {331}} \ right) \\ = (- 1) \ left ({\ frac {331} {3}} \ right) \ left ({\ frac {331} {5}} \ right) (- 1) \ left ({\ frac {331} {7}} \ right) (- 1) \ left ({\ frac {331} {23}} \ right) \\ = - \ left ({\ frac {1} {3}} \ right) \ left ({\ frac {1} {5}} \ right) \ left ({\ frac {2} {7}} \ right) \ left ({\ frac {9} {23}} \ right) \\ = - \ left ({\ frac {1} {3}} \ right) \ left ({\ frac {1} {5}} \ right) \ left ({\ frac {2} {7}} \ right) \ left ({\ frac {3 ^ {2}} {23}} \ right) \\ = - (1) (1) (1) (1) \\ = - 1. \ end {align}}

Или используя более эффективное вычисление:

(12345 331) = (98 331) = (2 ⋅ 7 2 331) = (2 331) = (- 1) 331 2 - 1 8 = - 1. {\ displaystyle \ left ({\ frac {12345} {331}} \ right) = \ left ({\ frac {98} {331}} \ right) = \ left ({\ frac {2 \ cdot 7 ^ {2}} {331}} \ right) = \ left ({\ frac {2} {331}} \ right) = (- 1) ^ {\ tfrac {331 ^ {2} -1} {8}} = - 1.}

\ left ({\ frac { 12345} {331}} \ right) = \ left ({\ frac {98} {331}} \ right) = \ left ({\ frac {2 \ cdot 7 ^ {2}} {331}} \ right) = \ left ({\ frac {2} {331}} \ right) = (- 1) ^ {\ tfrac {331 ^ {2} -1} {8}} = - 1.

В статье символ Якоби есть больше примеров манипуляции с символом Лежандра.

Примечания

Ссылки

Гаусс, Карл Фридрих; Мазер, Х. (переводчик на немецкий) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел) (второе издание), Нью-Йорк: Челси, ISBN 0-8284 -0191-8
Гаусс, Карл Фридрих; Кларк, Артур А. (переводчик на английский) (1986), Disquisitiones Arithmeticae (второе, исправленное издание), Нью-Йорк: Springer, ISBN 0-387-96254- 9
Бах, Эрик; Шаллит, Джеффри (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0-262-02405-5
Харди, GH ; Райт, EM (1980), Введение в теорию чисел (пятое издание), Оксфорд: Oxford University Press, ISBN 978-0 -19-853171-5
Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе издание), Нью-Йорк: Springer, ISBN 0-387-97329-X
Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна, Берлин: Springer, ISBN 3-540-66957-4
Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел, Нью-Йорк: Springer, ISBN 0-387-94457-5

Внешние ссылки

Калькулятор символа Якоби