Открыть главное меню

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

ФормулировкаПравить

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

 

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

 


ДоказательствоПравить

1. Пусть   — ненулевой остаток по модулю  . Обозначим через   следующий остаток по модулю  :

 

Тогда по малой теореме Ферма

 

Поэтому

 

Таким образом   сравним либо с   либо с   по модулю  . То есть

 

либо

 

2. Пусть   является квадратичным вычетом по модулю  . Тогда существует такое число  , что:

 

Поэтому

  (по малой теореме Ферма).

3. Рассмотрим многочлен:

 

Как доказано выше, любой квадратичный вычет является его корнем. Так как число   — простое, то остатки по модулю   образуют поле, поэтому многочлен не может иметь по модулю   больше корней чем его степень. Так как число квадратичных вычетов равно  , то они и только они являются корнями многочлена

 

Поэтому, если   является квадратичным невычетом по модулю  , то

 .

См. такжеПравить