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

Функция в теории чисел

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

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

Определение

Пусть – нечетное простое число . Целое число является квадратичным вычетом по модулю, если оно конгруэнтно совершенному квадрату по модулю , и является квадратичным невычетом по модулю в противном случае. Символ Лежандра является функцией и определяется как ${\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{ 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}}}$

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

${\displaystyle \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 последовательность является периодической с периодом p и иногда называется последовательностью Лежандра . Каждая строка в следующей таблице демонстрирует периодичность, как описано. ${\displaystyle \left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots }$

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

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

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

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

• Учитывая генератор , если , то является квадратичным вычетом тогда и только тогда, когда четно. Это показывает, что половина элементов в являются квадратичными остатками. ${\displaystyle g\in \mathbb {F} _{p}^{*}}$ ${\displaystyle x=g^{r}}$ ${\displaystyle x}$ ${\displaystyle r}$ ${\displaystyle \mathbb {F} _{p}^{*}}$
• Если тогда тот факт, что ${\displaystyle p\equiv 3{\text{ mod }}4}$

  ${\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {p+1}{2}}={\frac {(p-1)+2}{2}}={\frac {p-1}{2}}+1}$ дает нам, что это квадратный корень из квадратичного остатка . ${\displaystyle a=x^{(p+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}}\right).}$

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

  ${\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}}$

• Если рассматривать его как функцию от 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{cases}}}$

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

    ${\displaystyle \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,

    ${\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{ 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 — простое число, то

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Лежандр, AM (1798). Эссе по теории чисел. Париж. п. 186.
2. Харди и Райт, Thm. 83.
3. Рибенбойм, с. 64; Леммермейер, бывш. 2.25–2.28, стр. 73–74.
4. Гаусс, «Summierung gewisser Reihen von besonderer Art» (1811), перепечатано в Untersuchungen ... стр. 463–495.
5. Гаусс, «Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den Quadatischen Resten» (1818), перепечатано в Untersuruchungen ... стр. 501–505
6. Леммермейер, бывш. п. 31, 1.34
7. Леммермейер, стр. 236 и далее.

Рекомендации

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

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

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