Русская Википедия:Критерий Эйлера

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Пусть <math>p>2</math> простое. Число a, взаимно простое с <math>p</math>, является квадратичным вычетом по модулю <math>p</math> тогда и только тогда, когда

<math>a^{(p-1)/2}\equiv 1\mod p</math>

и является квадратичным невычетом по модулю <math>p</math> тогда и только тогда, когда

<math>a^{(p-1)/2}\equiv -1\mod p</math>

Литература

  • Михелович М.Х. Теория чисел. 1967. §3.9. с. 107—109