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

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

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


 пусть p>2 простое. Число a, взаимно простое с p, являетсяквадратичным вычетом по модулю p тогда и только тогда, когда
a(p1)/21modp
и является квадратичным невычетом помодулю p тогда и только тогда, когда
a(p1)/21modp

Доказательство


 1. Пусть a — ненулевой остаток по модулю p. Обозначим через xследующий остаток по модулю p:
xa(p1)/2modp
Тогда по малой теореме Ферма
x21modp
Поэтому
x21(x1)(x+1)0modp
Таким образом x сравнимлибо с 1 либо с 1 по модулю p. То есть
a(p1)/21modp
либо
a(p1)/21modp

 2. Пусть a является квадратичным вычетом по модулю p. Тогдасуществует такое число x, что:
x2amodp
Поэтому
a(p1)/2xp11modp
(по малой теореме Ферма).
 3. Рассмотрим многочлен:
x(p1)/21modp
Как доказано выше, любой квадратичный вычетявляется его корнем. Так как число p — простое, то остатки по модулюp образуют поле, поэтому многочлен не может иметь по модулю p большекорней чем его степень. Так как число квадратичных вычетов равно(p1)/2, то они и только они являются корнями многочлена
x(p1)/21modp
Поэтому, если a является квадратичнымневычетом по модулю p, то
a(p1)/21modp
.