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

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

[math]\displaystyle{ x^2 \equiv q \pmod p, }[/math]

[math]\displaystyle{ x^2 \equiv p \pmod q }[/math]

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

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

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

Если [math]\displaystyle{ p, q }[/math] — нечётные простые числа и хотя бы одно из них имеет вид [math]\displaystyle{ 4k + 1, }[/math] то либо оба [math]\displaystyle{ p, q }[/math] являются квадратичными вычетами по модулю друг друга, либо оба — невычеты. Если же [math]\displaystyle{ p, q }[/math] оба имеют вид [math]\displaystyle{ 4k + 3, }[/math] то квадратичным вычетом является одно и только одно из этих чисел — либо [math]\displaystyle{ p }[/math] по модулю [math]\displaystyle{ q, }[/math] либо [math]\displaystyle{ q }[/math] по модулю [math]\displaystyle{ p. }[/math]

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

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

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

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

Пояснения:
В	q является вычетом по модулю p	q ≡ 1 (mod 4) или p ≡ 1 (mod 4) (или оба)
Н	q является невычетом по модулю p	q ≡ 1 (mod 4) или p ≡ 1 (mod 4) (или оба)
В	q является вычетом по модулю p	оба q ≡ 3 (mod 4) и p ≡ 3 (mod 4)
Н	q является невычетом по модулю p	оба q ≡ 3 (mod 4) и p ≡ 3 (mod 4)

		3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
		q
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	В	Н	Н	В	Н	Н	Н	Н	Н	В	Н	Н	В	В	В	Н	В	Н	Н	В	В	Н	В

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

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

[math]\displaystyle{ \left(\frac pq\right)\left(\frac qp\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} }[/math]

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

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

[math]\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} }[/math]

[math]\displaystyle{ \left(\frac 2p\right) = (-1)^\frac{p^2-1}8 = \begin{cases}1&\text{если}&p\equiv \pm1\pmod 8,\\ -1&\text{если}&p\equiv \pm3\pmod 8,\end{cases} }[/math]

и

[math]\displaystyle{ \left(\frac ap\right) = \left(\frac aq\right) \quad \text{если} \quad p\equiv q\pmod{4a}. }[/math]

Следствия

Следующий факт, известный ещё Ферма: простыми делителями чисел [math]\displaystyle{ x^2 + 1 }[/math] могут быть лишь число 2 и простые числа, принадлежащие арифметической прогрессии
[math]\displaystyle{ 4k + 1. }[/math]

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

[math]\displaystyle{ x^2 + 1 \equiv 0 \pmod{p} }[/math]

по простому модулю [math]\displaystyle{ p \gt 2 }[/math] разрешимо в том и только в том случае, когда [math]\displaystyle{ p \equiv 1 \pmod 4. }[/math] С помощью символа Лежандра последнее утверждение может быть выражено следующим образом:

[math]\displaystyle{ \left(\frac{-1}p\right) = (-1)^\frac{p - 1}2. }[/math]

Вопрос о разрешимости сравнения
[math]\displaystyle{ ax^2 + bx + c \equiv 0 \pmod{p} }[/math]

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

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

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

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

[math]\displaystyle{ x^2\equiv 983\pmod{1103} }[/math]

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

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

[math]\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 }[/math]

История

Формулировка квадратичного закона взаимности была известна ещё Эйлеру в 1783 году^[3]. Лежандр сформулировал закон независимо от Эйлера и доказал его в некоторых частных случаях в 1785 году. Полное доказательство было опубликовано Гауссом в «Арифметических исследованиях» (1801 год); впоследствии Гаусс дал ещё несколько его доказательств, основанных на совершенно различных идеях.

Одно из самых простых доказательств было предложено Золотарёвым в 1872 году.^[4]^[5]^[6]

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

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

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

См. также

Примечания

↑ Карл Фридрих Гаусс. Труды по теории чисел / Общая редакция академика И. М. Виноградова, комментарии члена-корр. АН СССР Б. Н. Делоне. — М.: Изд-во АН СССР, 1959. — С. 126. — 297 с. — (Классики науки).
↑ Квадратичный вычет // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2. — С. 785—786.
↑ Euler, Opuscula analytica, Petersburg, 1783.
↑ 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. (недоступная ссылка)
↑ Прасолов В. В. Доказательство квадратичного закона взаимности по Золотарёву // Математическое просвещение. — 2000. — Т. 4. — С. 140—144.
↑ Горин Е. А. Перестановки и квадратичный закон взаимности по Золотарёву-Фробениусу-Руссо // Чебышевский сборник. — 2013. — Т. 14, вып. 4. — С. 80—94.
↑ Айерленд К., Роузен М. Классическое введение в современную теорию чисел.

Литература

Айерленд К., Роузен М. Классическое введение в современную теорию чисел. — Москва: Мир, 1987. — 428 с.
Бухштаб А. А. Теория чисел. — Москва: Просвещение, 1966.
Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952. — С. 180. — ISBN 5-93972-252-0.
Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — Москва: Физматлит, 1965. — С. 176. — ISBN 539701298X. — ISBN 9785397012980. Архивная копия от 30 сентября 2017 на Wayback Machine
Конвей Дж. Квадратичные формы, данные нам в ощущениях. — М.: МЦНМО, 2008. — 144 с. — 1000 экз. — ISBN 978-5-94057-268-8.
Хассе Г. Лекции по теории чисел. — Изд. иностранной литературы, 1953. — 527 с.

Ссылки

Львовский С. М. Квадратичный закон взаимности Архивная копия от 27 апреля 2016 на Wayback Machine Летняя школа «Современная математика», 2012, г. Дубна

[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.

[7] Айерленд К., Роузен М. Классическое введение в современную теорию чисел.

[1]

[2]

[3]

[4]

[5]

[6]

[7]