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

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

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

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

a^{(p-1)/2}\equiv 1\mod p

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

a^{(p-1)/2}\equiv -1\mod p


Доказательство[править | править исходный текст]

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

x \equiv a^{(p-1)/2} \mod p

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

x^2 \equiv 1 \mod p

Поэтому

x^2-1 \equiv (x-1)(x+1) \equiv 0 \mod p

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

a^{(p-1)/2}\equiv 1\mod p

либо

a^{(p-1)/2}\equiv -1\mod p

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

x^2\equiv a\mod p

Поэтому

a^{(p-1)/2}\equiv x^{p-1}\equiv 1 \mod p (по малой теореме Ферма).

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

x^{(p-1)/2}-1 \mod p

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

x^{(p-1)/2}-1 \mod p

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

a^{(p-1)/2} \equiv -1 \mod p.

См. также[править | править исходный текст]