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

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

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

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

a ( p − 1 ) / 2 ≡ 1 mod p {displaystyle a^{(p-1)/2}equiv 1mod p}

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

a ( p − 1 ) / 2 ≡ − 1 mod p {displaystyle a^{(p-1)/2}equiv -1mod p}