Математика / Арифметика и теория чисел

Закон квадратичной взаимности для двух простых чисел

Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.

Опубликовано: Обновлено:

Формула

$$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$
Схема Знак при перестановке
Остатки простых p и q по модулю 4q: 1q: 3p: 1p: 3+++−

Минус появляется в одном углу таблицы: p ≡ q ≡ 3 (mod 4).

Обозначения

$p,q$
Различные нечётные простые числа, —
$\left(\frac pq\right)$
Символ Лежандра числа p по модулю q, —
$\left(\frac qp\right)$
Символ после перестановки чисел, —

Условия применения

p и q — различные нечётные простые числа. Тогда оба символа ненулевые, а полуразности (p−1)/2 и (q−1)/2 целые. Приведение верхнего числа символа по нижнему допускается как до, так и после применения подходящего правила.

Ограничения

Формула не включает простое число 2 и не применяется при совпадении p и q. Для множителей 2 или −1 нужны дополнительные законы; для нечётного составного нижнего числа используют символ Якоби с иным смыслом результата.

Подробное объяснение

Пусть исходный вопрос — имеет ли p квадратный корень по модулю q. Обратный вопрос меняет роли простых чисел. Взаимность показывает, как из второго ответа восстановить первый: два символа совпадают в трёх случаях из четырёх, если различать остатки каждого простого числа по модулю 4.

Если простое число даёт остаток 1 по модулю 4, его полуразность (p−1)/2 чётна. Поэтому произведение полуразностей нечётно только для пары со значениями 3 и 3. Поскольку оба символа принимают значения ±1, умножение на известный символ равносильно делению на него.

Один из способов доказательства использует прямоугольник целочисленных пар с координатами от 1 до (p−1)/2 и от 1 до (q−1)/2. Наклонная прямая делит точки на две группы и не проходит ни через одну из них, поскольку p и q взаимно просты. Чётности размеров этих групп дают знаки двух символов по лемме Гаусса в форме для нечётного числителя.

Практический выигрыш появляется, когда после перестановки новый числитель приводят по малому модулю. Например, взамен символа с модулем 43 можно получить символ с модулем 7. Если остаток составной, верхнее число раскладывают на множители или применяют степенной критерий без дальнейших перестановок.

Как пользоваться формулой

  1. Убедитесь, что исходный символ относится к паре различных нечётных простых чисел; отдельно обработайте другие случаи.
  2. Вычислите оба остатка по модулю 4 и поставьте минус только для пары, в которой каждый остаток равен 3.
  3. Поменяйте местами p и q, затем замените верхнее число его наименьшим неотрицательным остатком по новому модулю.
  4. Найдите значение малого символа по списку квадратов или степени Эйлера и умножьте его на сохранённый знак.

Историческая справка

Лежандр обсуждал квадратичную взаимность в «Опыте о теории чисел», изданном в 1798 году. Гаусс в «Арифметических исследованиях» 1801 года дал доказательство и сформулировал результат в терминах вычетов и невычетов. Вместо формулы с произведением двух символов читатель раннего издания увидит случаи, разбираемые по остаткам простых чисел. У современной записи тот же смысл: один показатель чётности заменяет таблицу случаев. Это хороший пример того, как изменение обозначений сокращает вычисление без изменения содержания теоремы. Работы Эйлера и Лежандра относятся к этапу поиска и формулировки закономерности, а книгу Гаусса используют как первичный источник опубликованного доказательства.

Историческая линия формулы

Теорема выросла из работ Эйлера, Лежандра и Гаусса. С именем Гаусса связывают опубликованное доказательство 1801 года; привычная компактная запись через произведение символов Лежандра отличается от обозначений в этом первоисточнике.

Пример

Определим, существует ли квадратный корень из 7 по модулю 43. Оба числа простые и оба имеют вид 4k+3, поэтому при перестановке нужен минус. Получаем (7/43) = −(43/7). Число 43 даёт остаток 1 по модулю 7, а единица — квадрат. Значит, (7/43) = −(1/7) = −1, решения у сравнения x² ≡ 7 (mod 43) нет. Проверим без взаимности: 7² ≡ 6, 7⁴ ≡ 36, 7⁸ ≡ 6, 7¹⁶ ≡ 36 по модулю 43. Значит, 7²¹ ≡ 36·36·7 ≡ 6·7 = 42. Это остаток −1, как и предсказывает закон. Здесь нет округления: все операции выполняются над целыми остатками.

Частая ошибка

Меняют знак при одном остатке 3: нужны сразу два таких остатка. Вычисляют знак по остатку нового числителя после сокращения; следует взять исходную пару простых чисел. Переставляют составной верхний аргумент как простое число, не переходя к правилу Якоби и не раскладывая его на множители.

Практика

Задачи с решением

Перестановка без минуса

Условие. Вычислите (5/19).

Решение. Число 5 ≡ 1 (mod 4), поэтому (5/19) = (19/5) = (4/5) = 1.

Ответ. Число 5 — квадратичный вычет по модулю 19.

Два остатка 3

Условие. Вычислите (3/11).

Решение. Оба простых равны 3 по модулю 4. Значит, (3/11) = −(11/3) = −(2/3). Единственный ненулевой квадрат по модулю 3 — единица.

Ответ. Символ 1; проверка: 5² = 25 ≡ 3 (mod 11).

Дополнительные источники

  • https://dlmf.nist.gov/27.9
  • https://www.math.uni-bielefeld.de/~sieben/h284_gauss_1801.pdf
  • https://www.e-rara.ch/zut/content/titleinfo/1089237

Связанные формулы

Математика

Критерий Эйлера для квадратичных вычетов

$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p,\qquad \left(\frac ap\right)\in\{-1,0,1\}$

Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.

Математика

Символ Якоби по нечётному составному модулю

$n=\prod_{j=1}^r p_j^{e_j},\qquad \left(\frac an\right)=\prod_{j=1}^r\left(\frac{a}{p_j}\right)^{e_j}$

Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.