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

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

пусть $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$. См. также Малая теорема Ферма Многочлен