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

Квадратичный закон взаимности — ряд утверждений, касающихся разрешимости квадратичного сравнения по модулю. Согласно этому закону, если ${\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,q}$ — нечётные простые числа и хотя бы одно из них имеет вид ${\displaystyle 4k+1,}$ то либо оба ${\displaystyle p,q}$ являются квадратичными вычетами по модулю друг друга, либо оба — невычеты. Если же ${\displaystyle p,q}$ оба имеют вид ${\displaystyle 4k+3,}$ то квадратичным вычетом является одно и только одно из этих чисел — либо ${\displaystyle p}$ по модулю ${\displaystyle q,}$ либо ${\displaystyle q}$ по модулю ${\displaystyle p.}$

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

• ${\displaystyle \left({\frac {p}{q}}\right)=0}$, если ${\displaystyle p}$ делится нацело на ${\displaystyle q}$.
• ${\displaystyle \left({\frac {p}{q}}\right)=1}$, если ${\displaystyle p}$ является квадратичным вычетом по модулю ${\displaystyle q}$.
• ${\displaystyle \left({\frac {p}{q}}\right)=-1}$, если ${\displaystyle p}$ является квадратичным невычетом по модулю ${\displaystyle q}$.

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

Приведенная ниже таблица наглядно показывает, какие нечётные простые числа, не превышающие 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}$ могут быть лишь число 2 и простые числа, принадлежащие арифметической прогрессии

  ${\displaystyle 4k+1.}$

Более того, этот признак является и критерием, то есть сравнение

${\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].

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

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

См. также

• Символ Лежандра
• Символ Якоби
• Символ Кронекера — Якоби