Квадратичные вычеты

Определение и простые примеры

Квадратичный вычет - число по модулю простого числа p, которое является квадратичным вычетом означает, что существует целое x, удовлетворяющее $x^2 \equiv a \pmod p$.

Более формально, для простого нечетного p число a называется квадратичным вычетом по модулю p, если $\left(\frac{a}{p}\right)=1$. Если такого x не существует, говорят, что a — квадратичный невичет. Особая ситуация возникает, когда a сравнимо с нулём по модулю p: $a\equiv 0\pmod p$.

Символ Лежандра - для нечётного простого p и целого a символ Лежандра определяется следующим образом: $\left(\frac{a}{p}\right)=1$, $\left(\frac{a}{p}\right)=-1$ или $\left(\frac{a}{p}\right)=0$, в зависимости от случая.

Базовые свойства квадратичных вычетов

Символ Лежандра обладает важным свойством мультипликативности: для любых a и b справедливо $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. Это означает, что образование квадратичного вычета совместимо с умножением классов по модулю p.

Если a не делится на p и является квадратичным вычетом, то у сравнения $x^2 \equiv a \pmod p$ ровно два решения по модулю p — значения x и их противоположности. Отсюда следует, что неглавным образом решаемость имеет парность решений.

Если a делится на p, то символ Лежандра равен нулю: $\left(\frac{a}{p}\right)=0$, что отражает тривиальный случай.

Критерий Эйлера и теорема Ферма

Критерий Эйлера - для не делящегося на p целого a символ Лежандра выражается степенью по модулю p: $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$.

Критерий Эйлера извлекается из малой теоремы Ферма, которая гласит, что для a, взаимно простого с p, верно $a^{p-1}\equiv 1\pmod p$. Подняв a в степень (p-1)/2 и сравнивая с ±1 по модулю p, получаем критерий для принадлежности a множеству квадратичных вычетов.

Следствия критерия позволяют вычислять символ Лежандра при помощи простых степеней и сокращать задачи о существовании квадратичных корней к вычислению степеней по модулю.

Классические формулы: для −1 и для 2

Особые случаи часто встречаются и полезны при вычислениях. Для числа −1 формула даёт простое правило: $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$.

Для двойки существует известная явная формула: $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$. Эти формулы позволяют быстро определять, является ли −1 или 2 квадратичным вычетом по модулю данного простого p, не перебирая все возможные корни.

Такие частные формулы часто используются вместе с мультипликативностью символа Лежандра для разложения задачу на более простые множители.

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

Закон взаимности квадратов - центральный результат теории квадратичных вычетов, связывающий символы Лежандра с взаимно различными нечетными простыми p и q. Он формулируется как $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.

Закон говорит, что символы Лежандра «поменяются местами» с дополнительным знаком, зависящим от конгруэнтности простых по модулю 4. На практике это позволяет переводить вычисление $\frac{7^2-1}{8}=6$ в вычисление аналогичного символа с меньшим модулем и известным знаком.

Комбинация закона взаимности с формулами для −1 и 2 даёт простой и эффективный алгоритм вычисления символов для многих простых оснований.

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

Лемма Гаусса - один из удобных способов доказательства законов о квадратичных вычетах, утверждающий, что для взаимно простого a и нечетного простого p символ Лежандра выражается через знак произведения элементов арифметической прогрессии: {FORMULA_26}.

Определение экспоненты N в лемме формализуется так: {FORMULA_27}. Подсчёт N даёт алгебраическую интерпретацию символа и позволяет получить критерий через подсчёт перестановок и знаков.

Схема доказательства закона взаимности строится на сравнении двух способов оценки похожих произведений и применении леммы для различных a и p; технические детали сводятся к учёту чётности перестановок и парности чисел в соответствующих интервалах.

Символ Якоби и составные модули

Символ Якоби - обобщение символа Лежандра на произвольный нечётный положительный модуль n. Если разложение n задаётся как $\left(\frac{a}{n}\right)=\prod_{i}\left(\frac{a}{p_i}\right)^{e_i}$, то символ Якоби определяется как произведение соответствующих символов Лежандра: $\left(\frac{a}{n}\right)=-1$.

Важно помнить различие: если $\left(\frac{a}{p}\right)=(-1)^{N}$, то a гарантированно является квадратичным невичетом по крайней из простых составляющих, и значит не имеет квадратного корня по модулю n. Однако при $N=\#\{k:\;1\le k\le\frac{p-1}{2},\;ak\pmod p>\frac{p}{2}\}$ это не гарантирует существование корня по модулю n — символ Якоби равный единице не означает, что a является квадратичным вычетом по составному модулю.

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

Примеры и задачи

Типичная задача — найти, для каких простых p квадратный корень из данного числа a существует. Общая методика: факторизация, применение мультипликативности, использование частных формул и закона взаимности, затем проверка остаточных условий по простым делителям.

Практические упражнения: проверить, является ли 5 квадратичным вычетом по модулю различных простых; найти все квадратичные вычеты по модулю малого простого; применить символ Якоби для составного модуля и интерпретировать результат.

Приложения и дальнейшие направления

Теория квадратичных вычетов служит фундаментом для более общих теорий — например, для изучения вычетов степени k (н-та степени), теории полей вычетов и класс-поле. Она также важна в криптографии (например, в построении некоторых протоколов с доказательствами владения корнем), где используются вычисления символов и квадратичные резидуальные свойства.

Дальнейшие темы, которые логично изучить после квадратичных вычетов: обобщённые символы Гильберта, теория форм квадратичных, распределение квадратичных вычетов и аналитические методы их изучения.