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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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


Доказательство[править | править вики-текст]

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

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

Поэтому

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

либо

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

Поэтому

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

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

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

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

.

См. также[править | править вики-текст]