WikiSort.ru - Не сортированное

Критерий Эйлера позволяет определить является ли данное целое число квадратичным вычетом по модулю простого числа

Формулировка

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

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

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

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

Доказательство

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

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

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

${\displaystyle x^{2}\equiv 1\mod p}$

Поэтому

${\displaystyle x^{2}-1\equiv (x-1)(x+1)\equiv 0\mod p}$

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

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

либо

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

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

${\displaystyle x^{2}\equiv a\mod p}$

Поэтому

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

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

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

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

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

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

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

См. также

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