Квадратичный закон взаимности: золотая теорема Гаусса

Квадратичный закон взаимности - главная теорема элементарной теории чисел. Карл Фридрих Гаусс называл её «золотой теоремой» (aureum theorema) и нашёл восемь принципиально различных доказательств; современный счёт известных доказательств перевалил за двести. Содержательно закон даёт неожиданную симметрию: вопрос «является ли $p$ квадратом по модулю $q$» оказывается почти эквивалентен обратному - связь между двумя нечётными простыми задаётся аккуратной формулой через их остатки по модулю $4$.

Точная формулировка

Пусть $p$ и $q$ - различные нечётные простые. Квадратичный закон взаимности утверждает:

$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}}.$

Здесь $\left(\dfrac{a}{n}\right)$ - символ Лежандра, равный $+1$, если $a$ - квадратичный вычет по модулю $n$, и $-1$ иначе. Показатель $\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}$ чётен, если хотя бы одно из $p, q$ сравнимо с $1 \pmod 4$, и нечётен только когда оба числа сравнимы с $3 \pmod 4$. То есть символы всегда равны - кроме случая $p \equiv q \equiv 3 \pmod 4$, где они противоположны по знаку.

Пример. Для $p = 5$, $q = 13$ оба $\equiv 1 \pmod 4$: $\left(\dfrac{5}{13}\right) = \left(\dfrac{13}{5}\right) = \left(\dfrac{3}{5}\right) = -1$. Для $p = 3$, $q = 7$ оба $\equiv 3 \pmod 4$: $\left(\dfrac{3}{7}\right) = -\left(\dfrac{7}{3}\right) = -\left(\dfrac{1}{3}\right) = -1$, и действительно среди квадратов $1, 4, 2 \pmod 7$ тройки нет.

Два дополнения

К основной формуле добавляются два «дополнения», описывающие частные случаи числителя $-1$ и $2$. Первое даётся напрямую критерием Эйлера:

$\left(\dfrac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} +1, & p \equiv 1 \pmod 4, \\ -1, & p \equiv 3 \pmod 4. \end{cases}$

То есть $-1$ - квадрат по простому модулю $p$ тогда и только тогда, когда $p \equiv 1 \pmod 4$. Это утверждение восходит к Ферма и связано с его теоремой о представлении $p = x^2 + y^2$ ровно при $p \equiv 1 \pmod 4$.

Второе дополнение касается двойки и доказывается через лемму Гаусса либо через суммы Гаусса:

$\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} +1, & p \equiv \pm 1 \pmod 8, \\ -1, & p \equiv \pm 3 \pmod 8. \end{cases}$

Вместе с основной теоремой эти три формулы образуют полный набор: разложить числитель на простые, отдельно вынести $-1$ и степени $2$, остальные нечётные простые «перевернуть» по закону взаимности.

Исторический контекст

Идея скрытой симметрии между парами простых появилась задолго до Гаусса. Эйлер в работах 1740-х годов экспериментально обнаружил частные случаи: $\left(\dfrac{q}{p}\right)$ зависит только от $p \bmod 4q$ для фиксированного $q$. К полной формулировке он подошёл в посмертной статье Observationes circa divisionem quadratorum (1783), но строгого доказательства не дал. Лежандр в Essai sur la théorie des nombres (1798) выписал закон в современной форме, опираясь на недоказанную тогда гипотезу о простых в арифметических прогрессиях. Первое строгое доказательство принадлежит Гауссу, нашедшему его в 1796 году в возрасте 19 лет и опубликовавшему в Disquisitiones Arithmeticae (1801).

Восемь доказательств Гаусса идут через принципиально разные конструкции: индукция с леммой Гаусса, циклотомические периоды, квадратичные суммы Гаусса, подсчёт точек решётки в прямоугольнике (геометрическое доказательство Эйзенштейна позже стало классикой), теория квадратичных форм, произведения Якоби. Эта множественность подходов оказалась плодотворной - каждое доказательство открывало самостоятельное направление.

Обобщения: Якоби, Эйзенштейн, артиновская взаимность

Первое естественное обобщение - на составной знаменатель: символ Якоби $\left(\dfrac{a}{n}\right) = \prod_i \left(\dfrac{a}{p_i}\right)^{e_i}$ для нечётного $n = \prod p_i^{e_i}$. Закон взаимности для Якоби имеет ту же форму $\left(\dfrac{m}{n}\right)\left(\dfrac{n}{m}\right) = (-1)^{\tfrac{m-1}{2}\cdot\tfrac{n-1}{2}}$ для нечётных взаимно простых $m, n > 0$, и это позволяет вычислять символ за $O(\log^2 n)$ без знания факторизации - критически важно для криптографии.

Дальше идут кубический и биквадратичный законы (Эйзенштейн и Якоби): для кубических вычетов аналогом служит символ в кольце целых Эйзенштейна $\mathbb{Z}[\omega]$, $\omega = e^{2\pi i/3}$, для биквадратичных - в кольце целых Гаусса $\mathbb{Z}[i]$. Финальное обобщение - закон взаимности Артина (1927) в теории классовых полей: гомоморфизм Артина из группы дробных идеалов в группу Галуа абелева расширения описывает разложение простых идеалов. Все классические законы взаимности - частные случаи теоремы Артина, одна из вершин алгебраической теории чисел XX века и часть программы Ленглендса.

Алгоритм вычисления

Сводя три формулы вместе, получаем алгоритм типа Евклида:

1. Редукция: $a \gets a \bmod p$. Если $a = 0$, ответ $0$.
2. Знак: вынести $\left(\dfrac{-1}{p}\right) = (-1)^{(p-1)/2}$, если $a < 0$.
3. Двойки: вынести $\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8}$ для каждой степени $2$.
4. Взаимность: для нечётного простого $q$ - $\left(\dfrac{q}{p}\right) = \pm\left(\dfrac{p}{q}\right)$, знак по чётности $\tfrac{(p-1)(q-1)}{4}$.
5. Повторить для меньшего символа.

Пример: $\left(\dfrac{29}{53}\right)$. Оба $\equiv 1 \pmod 4$: $\left(\dfrac{29}{53}\right) = \left(\dfrac{53}{29}\right) = \left(\dfrac{24}{29}\right) = \left(\dfrac{2}{29}\right)^3 \cdot \left(\dfrac{3}{29}\right)$. $29 \equiv 5 \pmod 8$, значит $\left(\dfrac{2}{29}\right) = -1$, и $-\left(\dfrac{3}{29}\right) = -\left(\dfrac{29}{3}\right) = -\left(\dfrac{2}{3}\right) = +1$. Итог: $\left(\dfrac{29}{53}\right) = +1$. Битовая сложность - $O(\log^2 p)$, быстрее критерия Эйлера через возведение в степень.

Классическая задача: $-3$ как вычет

Элегантный результат - описание простых $p$, для которых $-3$ является квадратичным вычетом. По мультипликативности $\left(\dfrac{-3}{p}\right) = \left(\dfrac{-1}{p}\right) \cdot \left(\dfrac{3}{p}\right)$. Первый множитель равен $(-1)^{(p-1)/2}$. Для второго применим закон взаимности: $3 \equiv 3 \pmod 4$, поэтому $\left(\dfrac{3}{p}\right) = (-1)^{(p-1)/2} \cdot \left(\dfrac{p}{3}\right)$. Перемножая, знаки $(-1)^{(p-1)/2}$ сокращаются, и $\left(\dfrac{-3}{p}\right) = \left(\dfrac{p}{3}\right)$. А $\left(\dfrac{p}{3}\right) = +1$ ровно при $p \equiv 1 \pmod 3$. Итог: $-3$ - квадратичный вычет по простому $p > 3$ тогда и только тогда, когда $p \equiv 1 \pmod 3$, или $p \equiv 1, 7 \pmod{12}$.

Результат поразителен простотой: ответ зависит только от $p \bmod 3$, никакой связи с $4$ нет. Аналогичные «чистые» критерии получаются для любого фиксированного $a$ - это и есть содержательная сила закона взаимности.

Связь с разложением простых

Один из самых красивых выходов закона - теоремы о представимости простых в виде $p = x^2 + ny^2$. Ферма установил, что нечётное $p$ представимо как $x^2 + y^2$ при $p \equiv 1 \pmod 4$ (когда $\left(\dfrac{-1}{p}\right) = +1$), как $x^2 + 2y^2$ при $p \equiv 1, 3 \pmod 8$, как $x^2 + 3y^2$ при $p \equiv 1 \pmod 3$. Логика связи: $p = x^2 + ny^2$ означает $(-n) \equiv (x/y)^2 \pmod p$, поэтому необходимое условие - $\left(\dfrac{-n}{p}\right) = +1$, что переводится в условие на $p \bmod 4n$. Достаточность для малых $n$ доказали Ферма, Эйлер и Лагранж; для общих $n$ нужна теория главных форм и классов идеалов в $\mathbb{Z}[\sqrt{-n}]$, которую развил Гаусс.

Типовые задачи

Контрольные сводятся к четырём типам. Первый - посчитать конкретный символ Лежандра, прокрутив алгоритм до $\left(\dfrac{\pm 1}{q}\right)$. Второй - описать множество простых $p$, для которых $a$ - квадратичный вычет, в виде арифметических прогрессий по модулю $4a$ (для $a = -3$ это $p \equiv 1 \pmod 3$, для $a = 5$ - $p \equiv \pm 1 \pmod 5$). Третий - обосновать или опровергнуть представимость простого в виде $x^2 + ny^2$ для малых $n$. Четвёртый - доказать одно из дополнений, повторив рассуждение Гаусса с леммой о половинных вычетах.

Частые ошибки

• Применять к чётному простому. Закон взаимности - про различные нечётные простые. Двойка обрабатывается отдельной формулой $\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8}$, и подставлять $q = 2$ в основное тождество бессмысленно.
• Терять знак при перевороте. Если оба простых сравнимы с $3 \pmod 4$, символы противоположны: $\left(\dfrac{p}{q}\right) = -\left(\dfrac{q}{p}\right)$. Самая частая ошибка - забыть про этот случай и записать равенство со знаком плюс.
• Не редуцировать перед взаимностью. Применять закон к $\left(\dfrac{53}{7}\right)$ напрямую - лишний шаг; правильно сначала $53 \equiv 4 \pmod 7$, потом $\left(\dfrac{4}{7}\right) = +1$ без всякой взаимности.
• Путать с символом Якоби. Для составного знаменателя $\left(\dfrac{a}{n}\right) = +1$ не означает, что $a$ - квадрат. Классический контрпример $\left(\dfrac{2}{15}\right) = +1$, хотя $2$ - невычет по модулю $15$.
• Ошибка в показателе дополнения для 2. Формула $(-1)^{(p^2-1)/8}$ требует именно $p^2$, а не $p$. Для $p = 7$: $(p^2-1)/8 = 48/8 = 6$, чётно, $\left(\dfrac{2}{7}\right) = +1$ - действительно $3^2 = 9 \equiv 2 \pmod 7$.

FAQ

Почему закон называют «золотой теоремой»? Так его называл сам Гаусс - aureum theorema. Внешне это компактная формула об арифметических знаках, но из неё следуют десятки нетривиальных утверждений: критерии квадратичной вычетности, теоремы о разложении простых на квадраты, эффективные алгоритмы. Гаусс нашёл восемь принципиально различных доказательств, считая каждое самостоятельным открытием.

Чем закон взаимности отличается от критерия Эйлера? Критерий Эйлера $a^{(p-1)/2} \equiv \left(\dfrac{a}{p}\right) \pmod p$ - определение символа Лежандра через возведение в степень, без связи между двумя простыми. Закон взаимности - содержательная теорема, связывающая два разных символа через арифметику остатков. Алгоритмически он даёт $O(\log^2 p)$ вместо $O(\log^3 p)$, заменяя возведение в степень редукцией Евклида.

Какие есть обобщения? Прямое - символ Якоби для нечётных составных знаменателей с той же формулой. Дальше - кубический закон Эйзенштейна в $\mathbb{Z}[\omega]$ и биквадратичный Гаусса в $\mathbb{Z}[i]$. Финальное - закон взаимности Артина (1927) в теории классовых полей, описывающий разложение простых в абелевых расширениях; частный случай программы Ленглендса.

Коротко

Квадратичный закон взаимности связывает символы Лежандра $\left(\dfrac{p}{q}\right)$ и $\left(\dfrac{q}{p}\right)$ для различных нечётных простых формулой $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}}$: символы равны всегда, кроме случая $p \equiv q \equiv 3 \pmod 4$. Вместе с дополнениями для $-1$ и $2$ закон даёт алгоритм Евклида-стиля для вычисления любого символа за $O(\log^2 p)$ битовых операций. Гаусс называл теорему «золотой» и нашёл восемь доказательств; обобщения через символ Якоби, символы Эйзенштейна и артиновскую взаимность образуют центральную линию алгебраической теории чисел.