Критерий Эйлера

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

Этот критерий широко используется в теории чисел и алгоритмах: он позволяет быстро проверять квадратичность по модулю простого числа, что важно при решении сравнимостей, при вычислении корней по модулю p и в криптографии. В основе доказательства лежит обобщение — теорема Эйлера (Эйлерова теорема) для взаимно простых чисел и формула для функции Эйлера для простого модуля: $a^{\varphi(n)}\equiv1\pmod n$ и $\varphi(p)=p-1$. Из них следует нужное свойство степени, которое и даёт указанное соотношение с символом Лежандра.

Практически критерий применяется просто: возводят a в указанную степень по модулю p и смотрят на результат — если он сравним с единицей, то a является квадратичным вычетом, если со значением, эквивалентным −1, то не является. Ниже приведены простые иллюстрации вычислений.