Знак Лежандра

Знак Лежандра — это простая и удобная функция, которая показывает, является ли целое число квадратичным вычетом по модулю нечётного простого числа. Обозначают её как $\left(\frac{a}{p}\right)$. Для нечётного простого числа p и целого a значение определяется по правилам: $\displaystyle \left(\frac{a}{p}\right)=\begin{cases}0,&p\mid a\\1,&\text{если }\exists x:\;x^2\equiv a\pmod p\\-1,&\text{иначе}\end{cases}$ Этот компактный символ помогает классифицировать остатки по модулю p: если значение равно 1, то остаток представим как квадрат некоторого числа по модулю p; если −1, то не представим; если 0, то a кратно p.

Знак Лежандра обладает полезными свойствами, которые облегчают вычисления. В частности, он мультипликативен: $\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. Для быстрого вычисления часто применяют критерий Эйлера: $\displaystyle \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$, который позволяет через возведение в степень получить значение знака. Важным теоретическим результатом является закон квадратичной взаимности — он связывает знаки Лежандра для двух различных нечётных простых p и q: $\displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$. Кроме того, есть отдельная формула для числа 2: $\displaystyle \left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}$. Эти соотношения позволяют свести вычисления для больших чисел к более простым случаям.

Практическое применение знака Лежандра встречается при решении квадратных сравнений, в теории чисел и в криптографии: знание того, является ли число квадратичным вычетом, часто решает вопрос о существовании корней уравнения x^2≡a (mod p). Ниже приведены простые примеры расчёта.

Иллюстрация распределения квадратичных вычетов по модулю p может быть представлена схематически: {IMAGE_0}. Знак Лежандра остаётся фундаментальным инструментом в задачах, где требуется быстро определить наличие квадратного корня по модулю простого числа.