Критерий Эйлера (Tjnmyjnw |wlyjg)

Критерий Эйлера позволяет определить, является ли данное целое число квадратичным вычетом по модулю простого числа.

Формулировка

Пусть $p>2$ простое. Число a, взаимно простое с $p$ , является квадратичным вычетом по модулю $p$ тогда и только тогда, когда

a^{(p-1)/2}\equiv 1\mod p

и является квадратичным невычетом по модулю $p$ тогда и только тогда, когда

a^{(p-1)/2}\equiv -1\mod p