13-04-2023
Критерий Эйлера:
|
пусть простое. Число a, взаимно простое с , является квадратичным вычетом по модулю тогда и только тогда, когда и является квадратичным невычетом по модулю тогда и только тогда, когда |
1. Пусть — ненулевой остаток по модулю . Обозначим через следующий остаток по модулю :
Тогда по малой теореме Ферма
Поэтому
Таким образом сравним либо с либо с по модулю . То есть
либо
2. Пусть является квадратичным вычетом по модулю . Тогда существует такое число , что
Поэтому
3. Рассмотрим многочлен
Как доказано выше, любой квадратичный вычет является его корнем. Так как число — простое, то остатки по модулю образуют поле, поэтому многочлен не может иметь по модулю больше корней чем его степень. Так как число квадратичных вычетов равно , то они и только они являются корнями многочлена
Поэтому, если является квадратичным невычетом по модулю , то
Критерий Эйлера.