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

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

пусть $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$.

См. также

• Малая теорема Ферма
• Многочлен