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