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

Квадратичный закон взаимности — это фундаментальная теорема теории чисел, устанавливающая взаимосвязь между разрешимостью двух квадратичных сравнений по модулю простых чисел. В своей классической формулировке, сформулированной и впервые доказанной Карлом Фридрихом Гауссом в 1801 году, закон описывает, когда число \( p \) является квадратичным вычетом по модулю \( q \) и наоборот, где \( p \) и \( q \) — нечётные простые числа. Закон является одним из центральных результатов элементарной теории чисел и имеет многочисленные приложения в криптографии, алгебраической теории чисел и вычислительной математике.

История

Предыстория

Изучение квадратичных вычетов восходит к работам Пьера де Ферма (XVII век), который исследовал, какие простые числа представимы в виде \( x^2 + y^2 \). В XVIII веке Леонард Эйлер систематизировал эти наблюдения и сформулировал ряд гипотез, касающихся квадратичных вычетов. В 1772 году Эйлер высказал предположение, которое впоследствии стало частью квадратичного закона взаимности, но не смог его доказать. Адриен-Мари Лежандр в 1785 году ввёл символ, названный его именем, и опубликовал неполное доказательство закона, основанное на эвристических соображениях.

Доказательство Гаусса

Карл Фридрих Гаусс в своей монографии «Арифметические исследования» (лат. Disquisitiones Arithmeticae, 1801) привёл первое полное и строгое доказательство квадратичного закона взаимности. Гаусс назвал его «золотой теоремой» (лат. theorema aureum) и впоследствии опубликовал ещё пять различных доказательств. Его подход опирался на лемму Гаусса и метод математической индукции. Впоследствии было найдено более 200 различных доказательств закона, включая доказательства Эйзенштейна, Кронекера, Цоллера и других математиков.

Развитие в XIX–XX веках

После Гаусса квадратичный закон взаимности стал основой для развития теории полей классов и обобщённых законов взаимности. Эмми Нётер и Хельмут Хассе в начале XX века связали его с теорией алгебраических чисел. В 1920-х годах Эмиль Артин сформулировал общий закон взаимности для полей алгебраических чисел, который является одним из ключевых результатов современной теории чисел.

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

Символ Лежандра

Для нечётного простого числа \( p \) и целого числа \( a \), не делящегося на \( p \), символ Лежандра \(\left(\frac{a}{p}\right)\) определяется как:

• \( 1 \), если \( a \) является квадратичным вычетом по модулю \( p \) (то есть существует целое \( x \), такое что \( x^2 \equiv a \pmod{p} \)),
• \( -1 \), если \( a \) является квадратичным невычетом по модулю \( p \).

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

Пусть \( p \) и \( q \) — два различных нечётных простых числа. Тогда квадратичный закон взаимности утверждает: \[ \left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}. \] Иными словами, произведение символов Лежандра равно \( 1 \), если хотя бы одно из чисел \( p \) или \( q \) сравнимо с \( 1 \) по модулю \( 4 \), и равно \( -1 \), если оба числа сравнимы с \( 3 \) по модулю \( 4 \).

Дополнительные законы

К закону взаимности примыкают два дополнительных правила, которые позволяют вычислить символ Лежандра для \( a = 2 \) и \( a = -1 \):

• \(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\) (то есть \( -1 \) является квадратичным вычетом по модулю \( p \) тогда и только тогда, когда \( p \equiv 1 \pmod{4} \)),
• \(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\) (то есть \( 2 \) является квадратичным вычетом по модулю \( p \) тогда и только тогда, когда \( p \equiv \pm 1 \pmod{8} \)).

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

Доказательство Гаусса (метод индукции)

Гаусс использовал индукцию по простым числам. Его доказательство опирается на лемму Гаусса, которая выражает символ Лежандра через количество отрицательных вычетов в специальном наборе. Доказательство является конструктивным, но громоздким.

Доказательство Эйзенштейна (геометрическое)

Фердинанд Эйзенштейн в 1844 году предложил элегантное геометрическое доказательство, основанное на подсчёте точек с целыми координатами внутри прямоугольного треугольника. Этот метод использует симметрию и комбинаторные соображения.

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

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

Применение

Вычисление символа Лежандра

Квадратичный закон взаимности позволяет эффективно вычислять символ Лежандра для больших простых чисел, сводя задачу к последовательности меньших простых чисел. Например, для вычисления \(\left(\frac{357}{13}\right)\) можно разложить 357 на простые множители и применить закон.

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

В криптографии закон используется в алгоритмах, основанных на сложности задачи дискретного логарифмирования, а также в тестах простоты (например, тест Соловея — Штрассена). Проверка квадратичных вычетов применяется в протоколах обмена ключами и цифровых подписях.

Теория чисел

Закон является ключевым инструментом для изучения распределения квадратичных вычетов, решения диофантовых уравнений и доказательства теоремы о четырёх квадратах. Он также используется в теории квадратичных форм и решетах.

Примеры

Пример 1

Проверим, является ли 7 квадратичным вычетом по модулю 11. По закону взаимности: \[ \left(\frac{7}{11}\right) = \left(\frac{11}{7}\right) \cdot (-1)^{\frac{7-1}{2} \cdot \frac{11-1}{2}} = \left(\frac{4}{7}\right) \cdot (-1)^{3 \cdot 5} = \left(\frac{4}{7}\right) \cdot (-1)^{15} = -\left(\frac{4}{7}\right). \] Поскольку \( 4 \equiv 2^2 \pmod{7} \), \(\left(\frac{4}{7}\right) = 1\), следовательно, \(\left(\frac{7}{11}\right) = -1\), то есть 7 не является квадратичным вычетом по модулю 11.

Пример 2

Определим, является ли 2 квадратичным вычетом по модулю 17. По дополнительному закону для 2: \[ \left(\frac{2}{17}\right) = (-1)^{\frac{17^2-1}{8}} = (-1)^{\frac{289-1}{8}} = (-1)^{36} = 1, \] то есть 2 является квадратичным вычетом по модулю 17 (например, \( 6^2 = 36 \equiv 2 \pmod{17} \)).

Обобщения

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

Гаусс и Эйзенштейн разработали закон взаимности для кубических вычетов, используя кольцо целых гауссовых чисел \(\mathbb{Z}[\omega]\), где \(\omega\) — кубический корень из единицы. Этот закон связывает разрешимость сравнений \( x^3 \equiv a \pmod{p} \) для простых чисел специального вида.

Закон взаимности Артина

Эмиль Артин в 1927 году сформулировал общий закон взаимности для полей алгебраических чисел, который является центральным результатом теории полей классов. Он обобщает квадратичный закон на случай произвольных абелевых расширений.

Явный закон взаимности

В современной теории чисел существуют явные формулы для символа степенного вычета, включая закон взаимности Гильберта и символ Гильберта, которые используются в \( p \)-адическом анализе и арифметической геометрии.

Критика и ограничения

Квадратичный закон взаимности не имеет практических ограничений, однако его доказательство в классической формулировке требует аккуратного обращения с простыми числами. Для составных модулей закон не применим напрямую, и требуется использование символа Якоби или Кронекера, которые являются обобщениями символа Лежандра. Кроме того, закон не даёт конструктивного способа нахождения квадратного корня по модулю — для этого существуют отдельные алгоритмы, такие как алгоритм Тонелли — Шенкса.

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

• Гаусс в своей записной книжке называл квадратичный закон взаимности «жемчужиной арифметики».
• Существует более 200 различных доказательств закона, что делает его одной из самых доказываемых теорем в математике.
• В 2015 году математик Кеннет А. Рибет опубликовал доказательство, основанное на теории модулярных форм, что открыло новые связи с современной алгебраической геометрией.