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

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

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

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

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

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

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

Литература

• Михелович М.Х. Теория чисел. 1967. §3.9. с. 107—109