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

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

$x^2\equiv q(\mathrm{mod}p),$

$x^2\equiv p(\mathrm{mod}q)$

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

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

Если для заданных целых чисел $p,q$ сравнение $x^2\equiv p(\mathrm{mod}q)$ имеет решения, то $p$ называется квадратичным вычетом по модулю $q,$ а если решений нет, то — квадратичным невычетом по модулю $q.$ С использованием этой терминологии можно сформулировать квадратичный закон взаимности следующим образом: Шаблон:Рамка Если $p,q$ — нечётные простые числа и хотя бы одно из них имеет вид $4k+1,$ то либо оба $p,q$ являются квадратичными вычетами по модулю друг друга, либо оба — невычеты. Если же $p,q$ оба имеют вид $4k+3,$ то квадратичным вычетом является одно и только одно из этих чисел — либо $p$ по модулю $q,$ либо $q$ по модулю $p.$ |}

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

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

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

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

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

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

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{(p-1)(q-1)}{4}}=\{\begin{array}{ccccc}1& \text{если}& p\equiv 1(\mathrm{mod}4)& \text{или}& q\equiv 1(\mathrm{mod}4),\\ -1& \text{если}& p\equiv 3(\mathrm{mod}4)& \text{и}& q\equiv 3(\mathrm{mod}4),\end{array}$

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

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

$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{ccc}1& \text{если}& p\equiv 1(\mathrm{mod}4),\\ -1& \text{если}& p\equiv 3(\mathrm{mod}4),\end{array}$

$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{ccc}1& \text{если}& p\equiv \pm 1(\mathrm{mod}8),\\ -1& \text{если}& p\equiv \pm 3(\mathrm{mod}8),\end{array}$

и

$\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)\text{если}p\equiv q(\mathrm{mod}4a).$

Следствия

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

  $4k+1.$

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

$x^2+1\equiv 0(\mathrm{mod}p)$

по простому модулю $p>2$ разрешимо в том и только в том случае, когда $p\equiv 1(\mathrm{mod}4).$ С помощью символа Лежандра последнее утверждение может быть выражено следующим образом:

$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}.$

• Вопрос о разрешимости сравнения

  $a{x}^2+bx+c\equiv 0(\mathrm{mod}p)$

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

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

• Квадратичный закон позволяет быстро вычислять символы Лежандра. Например

  $\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$

Следовательно, сравнение

$x^2\equiv 983(\mathrm{mod}1103)$

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

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

$\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 году.

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Львовский С. М. Квадратичный закон взаимности Шаблон:Wayback Летняя школа «Современная математика», 2012, г. Дубна