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

Символ Лежандра — это удобная компактная запись, служащая для обозначения квадратичного характера целого числа по модулю простого. Формально символ записывают так: $\left(\frac{a}{p}\right)=\begin{cases}0,& p\mid a\\1,& a\not\equiv0\pmod p\ \text{и }a\text{ — квадратичный вычет}\\-1,&\text{иначе}\end{cases}$, где результат принимает три возможных значения: знак нуля означает делимость на модуль, единица — что число является квадратичным вычетом, а минус единица — что не является. Этот символ введён в классической теории чисел и используется там, где важно классифицировать элементы по тому, имеют ли они квадратный корень в кольце вычетов по простому модулю. Существуют также естественные обобщения символа Лежандра (например, символ Якоби и символ Кронекера), которые расширяют понятие на составные модули и на более общие ситуации.

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