Квадратичный закон взаимности

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Квадратичный закон взаимности — ряд утверждений, касающихся разрешимости квадратичного сравнения по модулю простого числа.

Формулировка[править | править вики-текст]

Квадратичный закон взаимности Гаусса для символов Лежандра утверждает, что

где р и q — различные нечётные простые числа.

Также справедливы следующие дополнения:

и

Следствия[править | править вики-текст]

  • Следующий факт, известный ещё Ферма: простыми делителями чисел могут быть лишь число 2 и простые числа, принадлежащие арифметической прогрессии
    .
Другими словами, сравнение
по простому модулю разрешимо в том и только в том случае, когда С помощью символа Лежандра, последнее утверждение может быть выражено следующим образом:
  • Вопрос о разрешимости сравнения
решается алгоритмом с использованием мультипликативности символа Лежандра и квадратичного закона взаимности.

Примеры использования[править | править вики-текст]

  • Квадратичный закон позволяет быстро вычислять символы Лежандра. Например
В частности сравнение
имеет решение.
  • Если использовать аналог закона взаимности для символа Якоби, то вычисление проходит ещё проще, поскольку более нет необходимости раскладывать числитель символа на простые множители.

История[править | править вики-текст]

Формулировка квадратичного закона взаимности была известна ещё Эйлеру в 1783 году[1] Лежандр сформулировал закон независимо от Эйлера и доказал его в некоторых частных случаях в 1785 году. Полное доказательство было получено Гауссом в 1796 году, который впоследствии дал несколько его доказательств, основанных на совершенно различных идеях.

Одно из самых простых доказательств было предложено Золотарёвым в 1872 году.[2][3][4]

В дальнейшем были получены различные обобщения квадратичного закона взаимности[5].

Вариации и обобщения[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Euler, Opuscula analytica, Petersburg, 1783.
  2. Zolotareff G. (1872). «Nouvelle démonstration de la loi de de réciprocité de Legendre». Nouvelles Annales de Mathématiques, 2e série 11: 354—362.
  3. Прасолов В. В. Доказательство квадратичного закона взаимности по Золотареву // Математическое просвещение. — 2000. — Т. 4. — С. 140—144.
  4. Горин Е. А. Перестановки и квадратичный закон взаимности по Золотареву-Фробениусу-Руссо // Чебышевский сборник. — 2013. — Т. 14, вып. 4. — С. 80-94.
  5. Айерленд К., Роузен М. Классическое введение в современную теорию чисел.