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

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

История

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

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

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

Закон квадратичной взаимности формулируется с помощью символа Лежандра. Для нечётного простого числа \(p\) и целого числа \(a\), не делящегося на \(p\), символ Лежандра \(\left(\frac{a}{p}\right)\) равен 1, если \(a\) является квадратичным вычетом по модулю \(p\) (то есть существует такое \(x\), что \(x^2 \equiv a \pmod{p}\)), и равен -1, если \(a\) является квадратичным невычетом.

Основная теорема

Пусть \(p\) и \(q\) — два различных нечётных простых числа. Тогда:

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

Или, что эквивалентно:

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

Словесная формулировка

Закон можно сформулировать следующим образом:

• Если хотя бы одно из чисел \(p\) или \(q\) даёт остаток 1 при делении на 4, то \(\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)\).
• Если оба числа \(p\) и \(q\) дают остаток 3 при делении на 4, то \(\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)\).

Дополнительные формулы

Для полноты закона необходимы также формулы для символа Лежандра для чисел 2 и -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}\)).

Примеры применения

Пример 1: Определение квадратичного вычета

Определим, является ли 7 квадратичным вычетом по модулю 11.

Вычисляем символ Лежандра \(\left(\frac{7}{11}\right)\). По закону взаимности:

\[ \left(\frac{7}{11}\right) = \left(\frac{11}{7}\right) \cdot (-1)^{\frac{7-1}{2} \cdot \frac{11-1}{2}} = \left(\frac{11}{7}\right) \cdot (-1)^{3 \cdot 5} = \left(\frac{11}{7}\right) \cdot (-1)^{15} = -\left(\frac{11}{7}\right) \]

Теперь вычисляем \(\left(\frac{11}{7}\right)\). Поскольку \(11 \equiv 4 \pmod{7}\), то \(\left(\frac{11}{7}\right) = \left(\frac{4}{7}\right)\). Так как 4 — это полный квадрат (\(2^2\)), то \(\left(\frac{4}{7}\right) = 1\). Следовательно, \(\left(\frac{7}{11}\right) = -1\). Это означает, что 7 не является квадратичным вычетом по модулю 11 (то есть не существует целого \(x\), такого что \(x^2 \equiv 7 \pmod{11}\)).

Пример 2: Проверка на простоту

Закон квадратичной взаимности используется в некоторых тестах на простоту, например, в тесте Соловея — Штрассена. Он основан на том, что для составного числа \(n\) существует не менее половины оснований \(a\), для которых символ Якоби (обобщение символа Лежандра на составные модули) не удовлетворяет закону взаимности.

Связанные понятия

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

Основной инструмент для формулировки закона. Определён для нечётного простого модуля \(p\) и целого числа \(a\), не кратного \(p\). Обладает свойствами мультипликативности и периодичности.

Символ Якоби

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

Символ Кронекера — Якоби

Дальнейшее обобщение, позволяющее рассматривать модули, включающие 2 и степени 2. Закон взаимности для него также существует, но формулируется сложнее.

Обобщения

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

• Кубическая взаимность — для кубических вычетов.
• Биквадратичная взаимность — для вычетов четвёртой степени.
• Закон взаимности Артина — наиболее общая форма, связывающая символы степенных вычетов в полях алгебраических чисел.

Эти обобщения были развиты в XIX—XX веках такими математиками, как Эйзенштейн, Куммер, Гильберт, Такаги и Артин.

Значение в математике

Закон квадратичной взаимности имеет огромное значение для теории чисел и смежных областей:

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

Источники

• Гаусс, К. Ф. «Disquisitiones Arithmeticae» (1801).
• Виноградов, И. М. «Основы теории чисел» (любое издание).
• Айерлэнд, К., Роузен, М. «Классическое введение в современную теорию чисел».
• Ленг, С. «Алгебраическая теория чисел».
• Серр, Ж.-П. «Курс арифметики».