Закон взаимности квадратичных вычетов¶

Закон взаимности квадратичных вычетов — это фундаментальная теорема теории чисел, устанавливающая связь между разрешимостью двух квадратичных сравнений вида \(x^2 \equiv p \pmod{q}\) и \(x^2 \equiv q \pmod{p}\), где \(p\) и \(q\) — различные нечётные простые числа. Теорема позволяет определить, является ли одно простое число квадратичным вычетом по модулю другого, не выполняя непосредственных вычислений, а лишь анализируя остатки от деления этих чисел на 4. Закон был впервые сформулирован Карлом Фридрихом Гауссом в 1796 году, который назвал его «золотой теоремой» арифметики.

¶История

¶Предыстория

Понятие квадратичного вычета восходит к работам Пьера де Ферма (XVII век), который изучал свойства простых чисел, представимых в виде суммы двух квадратов. Однако систематическое исследование квадратичных вычетов началось с Леонарда Эйлера (XVIII век). Эйлер сформулировал ряд частных случаев закона взаимности, но не смог доказать его в общем виде. В 1744 году он опубликовал критерий, позволяющий проверять, является ли число квадратичным вычетом по модулю простого числа, который позже получил название критерия Эйлера.

¶Формулировка Гаусса

Карл Фридрих Гаусс в возрасте 19 лет (1796) открыл общий закон взаимности квадратичных вычетов. Он представил первое доказательство в своей книге «Арифметические исследования» (1801). Гаусс придавал этому результату огромное значение, называя его «основной теоремой» теории чисел. Впоследствии он опубликовал ещё семь различных доказательств закона, каждое из которых использовало разные методы — от элементарной комбинаторики до анализа бесконечных рядов.

¶Последующие обобщения

Закон взаимности квадратичных вычетов стал отправной точкой для развития теории полей классов и алгебраической теории чисел. В XIX веке Эрнст Куммер обобщил его на случай высших степеней (закон взаимности степенных вычетов), а Давид Гильберт в начале XX века сформулировал закон взаимности в терминах символов Гильберта. В 1920-х годах Эмиль Артин и Хельмут Хассе создали общую теорию полей классов, которая включает закон взаимности квадратичных вычетов как частный случай.

¶Формулировка

¶Классическая формулировка

Для двух различных нечётных простых чисел \(p\) и \(q\) закон взаимности квадратичных вычетов утверждает:

\[ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, \]

где \(\left(\frac{a}{b}\right)\) — символ Лежандра, равный 1, если \(a\) является квадратичным вычетом по модулю \(b\), и \(-1\) в противном случае. Если \(p\) или \(q\) равно 2, то закон принимает дополнительную форму:

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

¶Словесная интерпретация

Закон можно сформулировать без символов: если хотя бы одно из чисел \(p\) или \(q\) даёт остаток 1 при делении на 4, то сравнения \(x^2 \equiv p \pmod{q}\) и \(x^2 \equiv q \pmod{p}\) либо оба разрешимы, либо оба неразрешимы. Если же оба числа дают остаток 3 при делении на 4, то одно из сравнений разрешимо, а другое — нет.

¶Пример

Рассмотрим \(p = 5\) и \(q = 7\). Оба числа дают остаток 1 и 3 соответственно при делении на 4: \(5 \equiv 1 \pmod{4}\), \(7 \equiv 3 \pmod{4}\). Поскольку одно из них (5) даёт остаток 1, то по закону взаимности оба сравнения должны быть либо разрешимы, либо нет. Проверим: \(x^2 \equiv 5 \pmod{7}\) — решения нет, так как квадраты по модулю 7 дают остатки 0, 1, 2, 4. \(x^2 \equiv 7 \pmod{5}\) — это \(x^2 \equiv 2 \pmod{5}\), что также не имеет решения (квадраты по модулю 5: 0, 1, 4). Таким образом, оба сравнения неразрешимы, что соответствует закону.

¶Доказательства

¶Первое доказательство Гаусса

Первое доказательство Гаусса (1801) основано на индукции по простым числам и использовании леммы, известной как «лемма Гаусса». Эта лемма связывает символ Лежандра с количеством отрицательных остатков при умножении чисел на фиксированный множитель. Доказательство было громоздким, но строгим.

¶Элементарные доказательства

Впоследствии были найдены более простые доказательства, использующие только свойства целых чисел. Например, доказательство с помощью «суммы Гаусса» (квадратичной суммы) позволяет вывести закон взаимности из алгебраических тождеств. Другое элементарное доказательство, предложенное Фердинандом Айзенштейном, использует геометрическую интерпретацию — подсчёт точек решётки в прямоугольнике.

¶Доказательство через теорию полей классов

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

¶Применение

¶Криптография

Закон взаимности квадратичных вычетов используется в криптографических алгоритмах, основанных на сложности извлечения квадратного корня по модулю составного числа. Например, в криптосистеме Рабина (1979) безопасность основана на том, что для составного модуля \(n = pq\) задача нахождения квадратичных вычетов эквивалентна факторизации \(n\). Закон взаимности позволяет эффективно проверять, является ли число квадратичным вычетом по модулю \(p\) или \(q\), что необходимо для дешифрования.

¶Теория чисел

Закон является ключевым инструментом для решения задач о представимости чисел квадратичными формами. Например, с его помощью доказывается, что простое число \(p\) представимо в виде суммы двух квадратов тогда и только тогда, когда \(p \equiv 1 \pmod{4}\) или \(p = 2\). Также закон используется для вычисления символов Лежандра и Якоби, что необходимо для проверки простоты чисел (например, в тесте Соловея — Штрассена).

¶Алгоритмическая теория

В компьютерной алгебре закон взаимности применяется для построения эффективных алгоритмов вычисления символа Лежандра (алгоритм, основанный на законе взаимности, работает за логарифмическое время). Это важно для криптографии с открытым ключом, где часто требуется проверка квадратичных вычетов.

¶Интересные факты

Гаусс назвал закон взаимности «золотой теоремой» арифметики и включил его в свою книгу «Арифметические исследования» как один из центральных результатов.
Существует более 200 различных доказательств закона взаимности квадратичных вычетов, включая доказательства, использующие топологию, комплексный анализ и алгебраическую геометрию.
В 1994 году математик Питер Сарнак доказал, что закон взаимности квадратичных вычетов эквивалентен некоторым свойствам случайных матриц в теории чисел.
Закон взаимности квадратичных вычетов является частным случаем более общего закона взаимности Артина, который играет центральную роль в современной теории полей классов.

¶Источники

Гаусс К. Ф. «Арифметические исследования» (1801).
Виноградов И. М. «Основы теории чисел» (любое издание).
Айерленд К., Роузен М. «Классическое введение в современную теорию чисел» (1982).
Боревич З. И., Шафаревич И. Р. «Теория чисел» (1964).
Серр Ж.-П. «Курс арифметики» (1973).