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

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

В теории чисел символ Лежандра — это мультипликативная функция со значениями 1, −1, 0, которая является квадратичным символом по модулю нечетного простого числа p : ее значение при (ненулевом) квадратичном вычете по модулю  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] Таким образом, вклад Лежандра заключался во введении удобной нотации , которая записывала квадратичную вычетность a  mod  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. Харди и Райт, Теория 83.
3. Рибенбойм, стр. 64; Леммермейер, ex. 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 denquaratischen Resten» (1818), переиздано в Untersuchungen ... стр. 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 , 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

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

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