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

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

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

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

Определение

Позвольте быть нечетным простым числом . Целое число является квадратичным вычетом по модулю, если оно сравнимо с полным квадратом по модулю, и квадратичным невычетом по модулю в противном случае. Символ Лежандра является функцией и определяется как ${\ displaystyle p}$ ${\ displaystyle a}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle a}$ ${\ displaystyle 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 & {\ текст {if}} a \ Equiv 0 {\ pmod {p}}. \ end {case}}}

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

{\ 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 \}.}

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

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

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

а п	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 . То есть, для генератора if then является квадратичным вычетом тогда и только тогда, когда он четный. Это также показывает, что половина ненулевых элементов в являются квадратичными вычетами. ${\ displaystyle g \ in \ mathbb {F} _ {p} ^ {*}}$ ${\ Displaystyle х = г ^ {г}}$ ${\ displaystyle x}$ ${\ displaystyle r}$ ${\ Displaystyle \ mathbb {F} _ {p} ^ {*}}$
Если тогда то, что ${\ Displaystyle п \ эквив 3 {\ текст {мод}} 4}$
${\ displaystyle {\ frac {p + 1} {4}} + {\ frac {p + 1} {4}} = {\ frac {(p-1) +2} {2}}}$ дает нам квадратный корень из квадратичного вычета . ${\ Displaystyle а = х ^ {(р + 1) / 4}}$ ${\ displaystyle x}$
Символ Лежандра периодичен по своему первому (или главному) аргументу: если a ≡ b (mod p ), то
${\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right).}$
Символ Лежандра является полностью мультипликативной функцией своего главного аргумента:
${\ displaystyle \ left ({\ frac {ab} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) \ left ({\ frac {b} {p}} \ Правильно).}$
В частности, произведение двух чисел, которые одновременно являются квадратичными остатками или квадратичными невычетами по модулю p, является остатком, тогда как произведение остатка с невычетом является невычетом. Особым случаем является символ Лежандра квадрата:
${\ displaystyle \ left ({\ frac {x ^ {2}} {p}} \ right) = {\ begin {cases} 1 & {\ mbox {if}} p \ nmid x \\ 0 & {\ mbox {если }} p \ mid x. \ end {case}}}$
Если рассматривать как функцию от a , символ Лежандра представляет собой уникальный квадратичный (или порядка 2) символ Дирихле по модулю p . ${\ displaystyle \ left ({\ frac {a} {p}} \ right)}$
Первое дополнение к закону квадратичной взаимности:
${\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 & {\ mbox { if}} p \ Equiv 1 {\ pmod {4}} \\ - 1 & {\ mbox {if}} p \ Equiv 3 {\ pmod {4}}. \ end {cases}}}$
Второе дополнение к закону квадратичной взаимности:
${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ tfrac {p ^ {2} -1} {8}} = {\ begin {cases} 1 & { \ mbox {if}} p \ Equiv 1 {\ mbox {or}} 7 {\ pmod {8}} \\ - 1 & {\ mbox {if}} p \ Equiv 3 {\ mbox {or}} 5 {\ pmod {8}}. \ end {case}}}$
Специальные формулы для символа Лежандра для малых значений a
: ${\ displaystyle \ left ({\ frac {a} {p}} \ right)}$ ${\ displaystyle \ left ({\ frac {a} {p}} \ right)}$
- Для нечетного простого числа p ≠ 3
  ${\ displaystyle \ left ({\ frac {3} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {p + 1} {6}} {\ big \ rfloor} } = {\ begin {case} 1 & {\ mbox {if}} p \ Equiv 1 {\ mbox {or}} 11 {\ pmod {12}} \\ - 1 & {\ mbox {if}} p \ Equiv 5 {\ mbox {или}} 7 {\ pmod {12}}. \ end {case}}}$
- Для нечетного простого числа p ≠ 5
  ${\ displaystyle \ left ({\ frac {5} {p}} \ right) = (- 1) ^ {{\ big \ lfloor} {\ frac {2p + 2} {5}} {\ big \ rfloor} } = {\ begin {cases} 1 & {\ mbox {if}} p \ Equiv 1 {\ mbox {or}} 4 {\ pmod {5}} \\ - 1 & {\ mbox {if}} p \ Equiv 2 {\ mbox {или}} 3 {\ pmod {5}}. \ end {case}}}$
Чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... определяются повторения F ₁ = F ₂ = 1, Р _{п + 1} = Р _п + Р _{п -1} . Если p - простое число, то
${\ Displaystyle F_ {p- \ left ({\ frac {p} {5}} \ right)} \ Equiv 0 {\ pmod {p}}, \ qquad F_ {p} \ Equiv \ left ({\ frac { p} {5}} \ right) {\ pmod {p}}.}$

Например,

{\ 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 - разные нечетные простые числа. Используя символ Лежандра, можно кратко сформулировать квадратичный закон взаимности :

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

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

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

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

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

{\ 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}}}

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

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

{\ 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) .}

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

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

{\ 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)}}.}

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

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

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

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

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

{\ 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}} \ right) \ left ({\ frac {1} {5}} \ right) \ left ({\ frac {2} {7}} \ right) \ left ( {\ frac {3 ^ {2}} {23}} \ right) \\ & = - (1) (1) (1) (1) \\ & = - 1. \ end {align}}}

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

{\ 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.}

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

Примечания

использованная литература

Гаусс, Карл Фридрих; Мазер, Х. (перевод на немецкий) (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
Харди, GH ; Райт, EM (1980), Введение в теорию чисел (пятое издание) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
Ирландия, Кеннет; Розен, Майкл (1990), Классическое введение в современную теорию чисел (второе издание) , Нью-Йорк: Спрингер , ISBN 0-387-97329-X
Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4
Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел , Нью-Йорк: Springer , ISBN 0-387-94457-5

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

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

Languages

In other projects