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

Квадратичный закон взаимности — ряд утверждений, касающихсяразрешимости квадратичного сравнения по модулю. Согласно этому закону,если 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году.
 В дальнейшем были получены различные обобщения квадратичного законавзаимности.

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



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