Математика / Арифметика и теория чисел
Закон квадратичной взаимности для двух простых чисел
Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.
Формула
Минус появляется в одном углу таблицы: 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. Если остаток составной, верхнее число раскладывают на множители или применяют степенной критерий без дальнейших перестановок.
Как пользоваться формулой
- Убедитесь, что исходный символ относится к паре различных нечётных простых чисел; отдельно обработайте другие случаи.
- Вычислите оба остатка по модулю 4 и поставьте минус только для пары, в которой каждый остаток равен 3.
- Поменяйте местами p и q, затем замените верхнее число его наименьшим неотрицательным остатком по новому модулю.
- Найдите значение малого символа по списку квадратов или степени Эйлера и умножьте его на сохранённый знак.
Историческая справка
Лежандр обсуждал квадратичную взаимность в «Опыте о теории чисел», изданном в 1798 году. Гаусс в «Арифметических исследованиях» 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
Связанные формулы
Математика
Критерий Эйлера для квадратичных вычетов
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Математика
Символ Якоби по нечётному составному модулю
Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.
Математика
Малая теорема Ферма: степени по простому модулю
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.