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

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

x2q(modp)
x2p(modq)
  либо оба имеют решения для x, либо оба не имеют. Поэтому в названии закона используется слово «взаимность». Если же p,q оба имеют вид 4k+3, то решение имеет одно и только одно из указанных сравнений.

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


 Если для заданных целых чисел p,q сравнение x2p(modq) имеет решения, то p называется квадратичным вычетом по модулю q,, а если решений нет, то — квадратичным невычетом по модулю q. С использованием этой терминологии можно квадратичный закон взаимности сформулировать следующим образом: Если p,q — нечётные простые числа и хотя бы одно из них имеет вид 4k+1, то либо оба p,q являются квадратичными вычетами по модулю друг друга, либо оба — невычеты. Если же p,q оба имеют вид 4k+3, то квадратичным вычетом является одно и только одно из этих чисел — либо p по модулю q, либо q по модулю p. \}
 Пусть p — целое число, q — нечётное простое число. Символ Лежандра (pq) определяется следующим образом.

  • (pq)=0, если  p делится нацело на  q.
  • (pq)=1, если  p является квадратичным вычетом по модулю  q.
  • (pq)=1, если  p является квадратичным невычетом по модулю  q.

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


 Приведенная ниже таблица (матрица) наглядно показывает, какие нечётные простые числа, не превышающие 100, являются вычетами, а какие — невычетами. Например, первая строка относится к модулю 3 и означает, что число 5 является квадратичным невычетом (Н), 7 является вычетом (В), 11 — невычетом и т. д. По таблице ясно видно, что для чисел вида 4k+1 (зелёные и синие клетки) все коды, симметричные им относительно главной диагонали матрицы, в точности такие же, что и означает «взаимность». Например, в клетке (5, 7) тот же код, что и в клетке (7, 5). А если клетки соответствуют двум числам вида 4k+3 (жёлтые и красные клетки) то коды противоположны — например, для (11, 19).
q
35
p3
5Н
7Н
11В
13В
17Н
19Н
23В
29Н
31Н
37В
41Н
43Н
47В
53Н
59В
61В
67Н
71В
73В
79Н
83В
89Н
97В

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


 Квадратичный закон взаимности Гаусса для символов Лежандра утверждает, что
(pq)(qp)=(1)(p1)(q1)4={1еслиp1(mod4)илиq1(mod4),1еслиp3(mod4)иq3(mod4),
где р и q — различные нечётные простые числа.
 Также справедливы следующие дополнения:
(1p)=(1)p12={1еслиp1(mod4),1еслиp3(mod4),

(2p)=(1)p218={1еслиp±1(mod8),1еслиp±3(mod8),
и
(ap)=(aq)еслиpq(mod4a).

Следствия



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


  Другими словами, сравнение
x2+10(modp)

 по простому модулю p>2 разрешимо в том и только в том случае, когда p1(mod4). С помощью символа Лежандра, последнее утверждение может быть выражено следующим образом:
(1p)=(1)p12.


  • Вопрос о разрешимости сравнения
    ax2+bx+c0(modp)


  решается алгоритмом с использованием мультипликативности символа Лежандра и квадратичного закона взаимности.

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



  • Квадратичный закон позволяет быстро вычислять символы Лежандра. Например
      :\{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

  Следовательно, сравнение
x2983(mod1103)

 имеет решение.

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



  \{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 году Лежандр сформулировал закон независимо от Эйлера и доказал его в некоторых частных случаях в 1785 году. Полное доказательство было опубликовано Гауссом в «Арифметических исследованиях» (1801 год); впоследствии Гаусс дал ещё несколько его доказательств, основанных на совершенно различных идеях.
 Одно из самых простых доказательств было предложено Золотарёвым в 1872 году.
 В дальнейшем были получены различные обобщения квадратичного закона взаимности.

Вариации и обобщения



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