ru.wikipedia.org

Квадратичный закон взаимности — Википедия

Квадратичный закон взаимности — ряд утверждений, касающихся разрешимости квадратичного сравнения по модулю. Согласно этому закону, если {\displaystyle p,q} — нечётные простые числа и хотя бы одно из них имеет вид {\displaystyle 4k+1,} то два сравнения

{\displaystyle x^{2}\equiv q{\pmod {p}},}
{\displaystyle x^{2}\equiv p{\pmod {q}}}

либо оба имеют решения для {\displaystyle x,} либо оба не имеют. Поэтому в названии закона используется слово «взаимность». Если же {\displaystyle p,q} оба имеют вид {\displaystyle 4k+3,} то решение имеет одно и только одно из указанных сравнений[1].

Если для заданных целых чисел {\displaystyle p,q} сравнение {\displaystyle x^{2}\equiv p{\pmod {q}}} имеет решения, то {\displaystyle p} называется квадратичным вычетом[2] по модулю {\displaystyle q,} а если решений нет, то — квадратичным невычетом по модулю {\displaystyle q.} С использованием этой терминологии можно сформулировать квадратичный закон взаимности следующим образом:

Пусть {\displaystyle p} — целое число, {\displaystyle q} — нечётное простое число. Символ Лежандра {\displaystyle \left({\frac {p}{q}}\right)} определяется следующим образом:

Приведенная ниже таблица наглядно показывает, какие нечётные простые числа, не превышающие 100, являются вычетами, а какие — невычетами. Например, первая строка относится к модулю 3 и означает, что число 5 является квадратичным невычетом (Н), 7 является вычетом (В), 11 — невычетом и т. д. По таблице ясно видно, что для чисел вида {\displaystyle 4k+1} (зелёные и синие клетки) все коды, симметричные им относительно главной диагонали матрицы, в точности такие же, что и означает «взаимность». Например, в клетке (5, 7) тот же код, что и в клетке (7, 5). Если же клетки соответствуют двум числам вида {\displaystyle 4k+3} (жёлтые и красные клетки), то коды противоположны — например, для (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 В Н Н В Н Н Н Н Н В Н Н В В В Н В Н Н В В Н В  

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

{\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}={\begin{cases}1&{\text{если}}&p\equiv 1{\pmod {4}}&{\text{или}}&q\equiv 1{\pmod {4}},\\-1&{\text{если}}&p\equiv 3{\pmod {4}}&{\text{и}}&q\equiv 3{\pmod {4}},\end{cases}}}

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

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

{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\text{если}}&p\equiv 1{\pmod {4}},\\-1&{\text{если}}&p\equiv 3{\pmod {4}},\end{cases}}}
{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1&{\text{если}}&p\equiv \pm 1{\pmod {8}},\\-1&{\text{если}}&p\equiv \pm 3{\pmod {8}},\end{cases}}}

и

{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)\quad {\text{если}}\quad p\equiv q{\pmod {4a}}.}
Более того, этот признак является и критерием, то есть сравнение
{\displaystyle x^{2}+1\equiv 0{\pmod {p}}}
по простому модулю {\displaystyle p>2} разрешимо в том и только в том случае, когда {\displaystyle p\equiv 1{\pmod {4}}.} С помощью символа Лежандра последнее утверждение может быть выражено следующим образом:
{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.}
  • Вопрос о разрешимости сравнения
    {\displaystyle ax^{2}+bx+c\equiv 0{\pmod {p}}}
решается алгоритмом с использованием мультипликативности символа Лежандра и квадратичного закона взаимности.
  • Квадратичный закон позволяет быстро вычислять символы Лежандра. Например
    {\displaystyle \left({\frac {983}{1103}}\right)=-\left({\frac {1103}{983}}\right)=-\left({\frac {120}{983}}\right)=-\left({\frac {2}{983}}\right)^{3}\cdot \left({\frac {3}{983}}\right)\cdot \left({\frac {5}{983}}\right)=\left({\frac {983}{3}}\right)\cdot \left({\frac {983}{5}}\right)=\left({\frac {2}{3}}\right)\cdot \left({\frac {3}{5}}\right)=\left({\frac {2}{3}}\right)^{2}=1}
Следовательно, сравнение
{\displaystyle x^{2}\equiv 983{\pmod {1103}}}
имеет решение.
  • Если использовать аналог закона взаимности для символа Якоби, то вычисление проходит ещё проще, поскольку более нет необходимости раскладывать числитель символа на простые множители.
{\displaystyle \left({\frac {983}{1103}}\right)=-\left({\frac {1103}{983}}\right)=-\left({\frac {120}{983}}\right)=-\left({\frac {2}{983}}\right)^{3}\cdot \left({\frac {15}{983}}\right)=\left({\frac {983}{15}}\right)=\left({\frac {8}{15}}\right)=\left({\frac {2}{15}}\right)^{3}=1}

Формулировка квадратичного закона взаимности была известна ещё Эйлеру в 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. ↑ Айерленд К., Роузен М. Классическое введение в современную теорию чисел.