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

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

либо оба имеют решения для либо оба не имеют. Поэтому в названии закона используется слово «взаимность». Если же оба имеют вид то решение имеет одно и только одно из указанных сравнений[1].

Связанные определения править

Если для заданных целых чисел   сравнение   имеет решения, то   называется квадратичным вычетом[2] по модулю   а если решений нет, то — квадратичным невычетом по модулю   С использованием этой терминологии можно сформулировать квадратичный закон взаимности следующим образом:

Если   — нечётные простые числа и хотя бы одно из них имеет вид   то либо оба   являются квадратичными вычетами по модулю друг друга, либо оба — невычеты. Если же   оба имеют вид   то квадратичным вычетом является одно и только одно из этих чисел — либо   по модулю   либо   по модулю  

Пусть   — целое число,   — нечётное простое число. Символ Лежандра   определяется следующим образом:

  •  , если   делится нацело на  .
  •  , если   является квадратичным вычетом по модулю  .
  •  , если   является квадратичным невычетом по модулю  .

Примеры взаимности для простых чисел от 3 до 97 править

Приведенная ниже таблица наглядно показывает, какие нечётные простые числа, не превышающие 100, являются вычетами, а какие — невычетами. Например, первая строка относится к модулю 3 и означает, что число 5 является квадратичным невычетом (Н), 7 является вычетом (В), 11 — невычетом и т. д. По таблице ясно видно, что для чисел вида   (зелёные и синие клетки) все коды, симметричные им относительно главной диагонали матрицы, в точности такие же, что и означает «взаимность». Например, в клетке (5, 7) тот же код, что и в клетке (7, 5). Если же клетки соответствуют двум числам вида   (жёлтые и красные клетки), то коды противоположны — например, для (11, 19).

Пояснения:
В q является вычетом по модулю p    q ≡ 1 (mod 4) или p ≡ 1 (mod 4) (или оба)  
Н q является невычетом по модулю p  
В q является вычетом по модулю p оба q ≡ 3 (mod 4) и p ≡ 3 (mod 4)
Н q является невычетом по модулю p  
q
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
p 3   Н В Н В Н В Н Н В В Н В Н Н Н В В Н В В Н Н В
5 Н   Н В Н Н В Н В В Н В Н Н Н В В Н В Н В Н В Н
7 Н Н   В Н Н Н В В Н В Н В Н В Н Н В В Н В Н Н Н
11 В В Н   Н Н Н В Н В В Н Н В В В Н В В Н Н Н В В
13 В Н Н Н   В Н В В Н Н Н В Н В Н В Н Н Н В Н Н Н
17 Н Н Н Н В   В Н Н Н Н Н В В В В Н В Н Н Н В В Н
19 Н В В В Н В   В Н Н Н Н В В Н Н В Н Н В Н В Н Н
23 В Н Н Н В Н Н   В В Н В Н В Н В Н Н В В Н Н Н Н
29 Н В В Н В Н Н В   Н Н Н Н Н В В Н В В Н Н В Н Н
31 Н В В Н Н Н В Н Н   Н В Н В Н В Н В В Н Н Н Н В
37 В Н В В Н Н Н Н Н Н   В Н В В Н Н В В В Н В Н Н
41 Н В Н Н Н Н Н В Н В В   В Н Н В В Н Н В Н В Н Н
43 Н Н Н В В В Н В Н В Н В   В В В Н В Н Н В В Н В
47 В Н В Н Н В Н Н Н Н В Н Н   В В В Н В Н В В В В
53 Н Н В В В В Н Н В Н В Н В В   В Н Н Н Н Н Н В В
59 В В В Н Н В В Н В Н Н В Н Н В   Н Н В Н В Н Н Н
61 В В Н Н В Н В Н Н Н Н В Н В Н Н   Н Н В Н В Н В
67 Н Н Н Н Н В В В В Н В Н Н В Н В Н   В В Н В В Н
71 В В Н Н Н Н В Н В Н В Н В Н Н Н Н Н   В В В В Н
73 В Н Н Н Н Н В В Н Н В В Н Н Н Н В В В   В Н В В
79 Н В Н В В Н В В Н В Н Н Н Н Н Н Н В Н В   В В В
83 В Н В В Н В Н В В В В В Н Н Н В В Н Н Н Н   Н Н
89 Н В Н В Н В Н Н Н Н Н Н Н В В Н Н В В В В Н   В
97 В Н Н В Н Н Н Н Н В Н Н В В В Н В Н Н В В Н В  

Формулировка с помощью символов Лежандра править

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

 

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

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

 
 

и

 

Следствия править

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

Примеры использования править

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

История править

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

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

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

Вариации и обобщения править

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

См. также править

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

  1. Карл Фридрих Гаусс. Труды по теории чисел / Общая редакция академика И. М. Виноградова, комментарии члена-корр. АН СССР Б. Н. Делоне. — М.: Изд-во АН СССР, 1959. — С. 126. — 297 с. — (Классики науки).
  2. Квадратичный вычет // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2. — С. 785—786.
  3. Euler, Opuscula analytica, Petersburg, 1783.
  4. Zolotareff G. Nouvelle démonstration de la loi de de réciprocité de Legendre (фр.) // Nouvelles Annales de Mathématiques, 2e série : magazine. — 1872. — Vol. 11. — P. 354—362. (недоступная ссылка)
  5. Прасолов В. В. Доказательство квадратичного закона взаимности по Золотарёву // Математическое просвещение. — 2000. — Т. 4. — С. 140—144.
  6. Горин Е. А. Перестановки и квадратичный закон взаимности по Золотарёву-Фробениусу-Руссо // Чебышевский сборник. — 2013. — Т. 14, вып. 4. — С. 80—94. Архивировано 4 марта 2016 года.
  7. Айерленд К., Роузен М. Классическое введение в современную теорию чисел.

Литература править

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