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