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

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

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

См. также

Категории:

Теория чисел
Теоремы

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное

Смотреть что такое "Критерий Эйлера" в других словарях:

критерий Эйлера — Критерий подобия полей давления, характеризует соотношение сил давления и инерции в потоке. [А.С.Гольдберг. Англо русский энергетический словарь. 2006 г.] Тематики энергетика в целом EN Euler criterionEuEuler number … Справочник технического переводчика
ЭЙЛЕРА ЧИСЛО — (по имени Л. Эйлера), один из подобия критериев движения жидкостей или газов. Характеризует соотношение между силами давления, действующими на элем. объём жидкости или газа, и инерционными силами. Э. ч. Eu=2(р2 p1/rv2 (иногда 2р/rv2), где р2, р1… … Физическая энциклопедия
Критерий подобия — Критерий подобия безразмерная величина, составленная из размерных физических параметров, определяющих рассматриваемое физическое явление. Равенство всех однотипных критериев подобия для двух физических явлений и систем необходимое и… … Википедия
Критерий Куранта — Фридрихса — Леви — (критерий КФЛ) необходимое условие устойчивости явного численного решения некоторых дифференциальных уравнений в частных производных. Как следствие, во многих компьютерных симуляциях временной шаг должен быть меньше определённого значения, иначе… … Википедия
Критерий Куранта — Фридрихса Леви (критерий КФЛ) необходимое условие устойчивости явного численного решения некоторых дифференциальных уравнений в частных производных. Как следствие, во многих компьютерных симуляциях временной шаг должен быть меньше определённого… … Википедия
Критерий подобия — [similarity criterion (parameter)] безразмерное соотношение, полученное из физических и геометрических параметров, характеризующих явление, которое в разных условиях для подобных систем должно быть равным. Критерий подобия используют для… … Энциклопедический словарь по металлургии
Эйлера число — один из подобия критериев (См. Подобия критерии) движения жидкостей или газов. Характеризует соотношение между силами давления, действующими на элементарный объём жидкости или газа, и инерционными силами. Э. ч. Eu определяют формулой… … Большая советская энциклопедия
Функция Эйлера — Не следует путать с функцией распределения простых чисел. Первая тысяча значений Функция Эйлера φ(n) мультипликативная … Википедия
ЭЙЛЕРА КРИТЕРИЙ — при а, не делящемся на простое число p>2, имеет место сравнение где Лежандра символ. Таким образом, Э. к. дает необходимое и достаточное условие того, чтобы число являлось квадратичным вычетом или же невычетом по модулю р. Доказан Л. Эйлером в… … Математическая энциклопедия
Число Эйлера (физика) — Число Эйлера ( ) безразмерный коэффициент, имеющий место в уравнениях Навье Стокса, описывающий отношение между силами давления на единичный объём жидкости (или газа) и инерционными силами. где плотность, перепад… … Википедия

Словари и энциклопедии на Академике

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

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

См. также

Полезное

Смотреть что такое "Критерий Эйлера" в других словарях:

Поделиться ссылкой на выделенное

Словари и энциклопедии на Академике

Википедия

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

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

См. также

Полезное

Смотреть что такое "Критерий Эйлера" в других словарях:

Поделиться ссылкой на выделенное

Прямая ссылка: