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

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

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

Определение [ править ]

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

\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a quadratic nonresidue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}

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

\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.

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

Таблица значений [ править ]

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

а п	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

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

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

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

Например,

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

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

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

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

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

Многие доказательства квадратичной взаимности основаны на критерии Эйлера.

\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {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}}

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

Кронекера Доказательство ^[6] впервые устанавливает, что

\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 , он получает соотношение между ( п д ) и ( д п ).

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

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

Вычислительный пример [ править ]

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

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

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

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

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

Поскольку эффективный алгоритм факторизации неизвестен, но известны эффективные алгоритмы модульного возведения в степень , в целом более эффективно использовать исходное определение Лежандра, например

{\begin{aligned}\left({\frac {98}{331}}\right)&\equiv 98^{\frac {331-1}{2}}&{\pmod {331}}\\&\equiv 98^{165}&{\pmod {331}}\\&\equiv 98\cdot (98^{2})^{82}&{\pmod {331}}\\&\equiv 98\cdot 5^{82}&{\pmod {331}}\\&\equiv 98\cdot 25^{41}&{\pmod {331}}\\&\equiv 133\cdot 25^{40}&{\pmod {331}}\\&\equiv 133\cdot 294^{20}&{\pmod {331}}\\&\equiv 133\cdot 45^{10}&{\pmod {331}}\\&\equiv 133\cdot 39^{5}&{\pmod {331}}\\&\equiv 222\cdot 39^{4}&{\pmod {331}}\\&\equiv 222\cdot 197^{2}&{\pmod {331}}\\&\equiv 222\cdot 82&{\pmod {331}}\\&\equiv -1&{\pmod {331}}\end{aligned}}

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

Примечания [ править ]

^ Лежандр, AM (1798). Очерк теории чисел . Париж. п. 186 .
^ Харди и Райт, Thm. 83.
^ Рибенбойм, с. 64; Леммермейер, бывш. 2.25–2.28, стр. 73–74.
^ Гаусс, «Суммирование некоторых рядов особого рода» (1811), перепечатано в «Исследованиях»... стр. 463–495.
^ Гаусс, «Новые доказательства и расширения основной теоремы в доктрине квадратных остатков» (1818), перепечатано в «Исследованиях» ... стр. 501–505.
^ Леммермейер, бывш. п. 31, 1.34
^ Леммермейер, стр. 236 и далее.

Ссылки [ править ]

Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике (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-Х
Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4
Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел , Нью-Йорк: Springer , ISBN 0-387-94457-5

Внешние ссылки [ править ]

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

[1] Лежандр, AM (1798). Очерк теории чисел . Париж. п. 186 .

[2] Харди и Райт, Thm. 83.

[3] Рибенбойм, с. 64; Леммермейер, бывш. 2.25–2.28, стр. 73–74.

[4] Гаусс, «Суммирование некоторых рядов особого рода» (1811), перепечатано в «Исследованиях»... стр. 463–495.

[5] Гаусс, «Новые доказательства и расширения основной теоремы в доктрине квадратных остатков» (1818), перепечатано в «Исследованиях» ... стр. 501–505.

[6] Леммермейер, бывш. п. 31, 1.34

[7] Леммермейер, стр. 236 и далее.

[1]

[2]

[3]

[4]

[5]

[6]

[7]