Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

См. такжеПравить

Викия-сеть

Случайная вики