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

Символ Лежандра (а/п)
для различных а (вверху) и п (по левой стороне).

а п	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 ≤ а < п показаны, так как из-за первого свойства под любым другим а может быть уменьшен по модулю п. Квадратичные вычеты выделены желтым цветом и точно соответствуют значениям 0 и 1.

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

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

Определение

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

${displaystyle left ({frac {a} {p}} ight) = {egin {cases} 1 & {ext {if}} a {ext {- квадратичный вычет по модулю}} p {ext {и}} aot Equiv 0 { pmod {p}}, - 1 & {ext {if}} a {ext {неквадратичный вычет по модулю}} p, 0 & {ext {if}} aequiv 0 {pmod {p}}. end {cases }}}$

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

${displaystyle left ({frac {a} {p}} ight) эквивалентно ^ {frac {p-1} {2}} {pmod {p}} quad {ext {and}} quad left ({frac {a} {p}} ight) в {-1,0,1}.}$

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

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

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

а п	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. То есть с учетом генератора ${displaystyle gin mathbb {F} _ {p} ^ {*}}$, если ${displaystyle x = g ^ {r}}$тогда ${displaystyle x}$ является квадратичным вычетом тогда и только тогда, когда ${displaystyle r}$ даже. Это также показывает, что половина ненулевых элементов в ${displaystyle mathbb {F} _ {p} ^ {*}}$ являются квадратичными вычетами.
• Если ${displaystyle pequiv 3 {ext {mod}} 4}$ то факт, что

  ${displaystyle {frac {p + 1} {4}} + {frac {p + 1} {4}} = {frac {(p-1) +2} {2}}}$ дает нам это ${displaystyle a = x ^ {(p + 1) / 4}}$ является квадратным корнем из квадратичного вычета ${displaystyle x}$.

• Символ Лежандра периодичен в своем первом (или верхнем) аргументе: если а ≡ б (мод п), тогда

  ${displaystyle left ({frac {a} {p}} ight) = left ({frac {b} {p}} ight).}$

• Символ Лежандра - это полностью мультипликативная функция его главного аргумента:

  ${displaystyle left ({frac {ab} {p}} ight) = left ({frac {a} {p}} ight) left ({frac {b} {p}} ight).}$

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

  ${displaystyle left ({frac {x ^ {2}} {p}} ight) = {egin {cases} 1 & {mbox {if}} pmid x 0 & {mbox {if}} pmid x.end {cases}} }$

• Если рассматривать как функцию а, символ Лежандра ${displaystyle left ({frac {a} {p}} ight)}$ единственная квадратичная (или порядка 2) Dirichlet персонаж по модулю п.
• Первое дополнение к закону квадратичной взаимности:

  ${displaystyle left ({frac {-1} {p}} ight) = (- 1) ^ {frac {p-1} {2}} = {egin {cases} 1 & {mbox {if}} pequiv 1 {pmod {4}} - 1 & {mbox {if}} pequiv 3 {pmod {4}}. End {cases}}}$

• Второе дополнение к закону квадратичной взаимности:

  ${displaystyle left ({frac {2} {p}} ight) = (- 1) ^ {frac {p ^ {2} -1} {8}} = {egin {cases} 1 & {mbox {if}} pequiv 1 {mbox {или}} 7 {pmod {8}} - 1 & {mbox {if}} pequiv 3 {mbox {или}} 5 {pmod {8}}. End {cases}}}$

• Специальные формулы для символа Лежандра ${displaystyle left ({frac {a} {p}} ight)}$ для малых значений а:
  • Для нечетного простого числа п ≠ 3,

    ${displaystyle left ({frac {3} {p}} ight) = (- 1) ^ {{ig lfloor} {frac {p + 1} {6}} {ig floor}} = {egin {case} 1 & { mbox {if}} pequiv 1 {mbox {or}} 11 {pmod {12}} - 1 & {mbox {if}} pequiv 5 {mbox {or}} 7 {pmod {12}}. end {cases}} }$

  • Для нечетного простого числа п ≠ 5,

    ${displaystyle left ({frac {5} {p}} ight) = (- 1) ^ {{ig lfloor} {frac {2p + 2} {5}} {ig floor}} = {egin {case} 1 & { mbox {if}} pequiv 1 {mbox {or}} 4 {pmod {5}} - 1 & {mbox {if}} pequiv 2 {mbox {or}} 3 {pmod {5}}. end {cases}} }$

• В Числа Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… определяются повторением F₁ = F₂ = 1, F_п+1 = F_п + F_п−1. Если п простое число, тогда

  ${displaystyle F_ {p-left ({frac {p} {5}} ight)} Equiv 0 {pmod {p}}, qquad F_ {p} Equiv left ({frac {p} {5}} ight) {pmod {п}}.}$

Например,

${displaystyle {egin {align} left ({frac {2} {5}} ight) & = - 1, & F_ {3} & = 2, & F_ {2} & = 1, left ({frac {3} { 5}} ight) & = - 1, & F_ {4} & = 3, & F_ {3} & = 2, left ({frac {5} {5}} ight) & = 0, & F_ {5} & = 5, && left ({frac {7} {5}} ight) & = - 1, & F_ {8} & = 21, & F_ {7} & = 13, left ({frac {11} {5}} ight) & = 1, & F_ {10} & = 55, & F_ {11} & = 89.end {выровнено}}}$

• Этот результат исходит из теории Последовательности Лукаса, которые используются в проверка на простоту.^[4] Видеть Стена – Солнце – Солнце премьер.

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

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

${displaystyle left ({frac {q} {p}} ight) left ({frac {p} {q}} ight) = (- 1) ^ {{frac {p-1} {2}} cdot {frac { q-1} {2}}}.}$

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

${displaystyle left ({frac {a} {p}} ight) эквивалентно ^ {frac {p-1} {2}} {pmod {p}}.}$

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

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

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

в его четвертом^[5] и шестой^[6] доказательства квадратичной взаимности.

• Кронекера доказательство^[7] сначала устанавливает, что

${displaystyle left ({frac {p} {q}} ight) = operatorname {sgn} left (prod _ {i = 1} ^ {frac {q-1} {2}} prod _ {k = 1} ^ { frac {p-1} {2}} left ({frac {k} {p}} - {frac {i} {q}} ight) ight).}$

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

• Один из Эйзенштейн доказательства^[8] начинается с демонстрации того, что

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

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

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

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

Расчетный пример

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

${displaystyle {egin {выравнивается} left ({frac {12345} {331}} ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left) ( {frac {823} {331}} ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left ({frac {161} {331} } ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left ({frac {7} {331}} ight) left ({frac { 23} {331}} ight) & = (- 1) left ({frac {331} {3}} ight) left ({frac {331} {5}} ight) (- 1) left ({frac { 331} {7}} ight) (- 1) left ({frac {331} {23}} ight) & = - left ({frac {1} {3}} ight) left ({frac {1} { 5}} ight) left ({frac {2} {7}} ight) left ({frac {9} {23}} ight) & = - left ({frac {1} {3}} ight) left ( {frac {1} {5}} ight) left ({frac {2} {7}} ight) left ({frac {3 ^ {2}} {23}} ight) & = - (1) (1 ) (1) (1) & = - 1.end {выровнено}}}$

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

${displaystyle left ({frac {12345} {331}} ight) = left ({frac {98} {331}} ight) = left ({frac {2cdot 7 ^ {2}} {331}} ight) = left ({frac {2} {331}} ight) = (- 1) ^ {frac {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), Алгоритмическая теория чисел (Том I: Эффективные алгоритмы), Кембридж: MIT Press, ISBN  0-262-02405-5
• Харди, Г. Х.; Райт, Э. М. (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

внешняя ссылка

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