Критерій Ейлера

У теорії чисел критерій Ейлера — це формула для визначення чи є ціле квадратичним лишком по простому модулю. А саме,

Нехай p буде непарним простим і a буде цілим числом взаємно простим з p. Тоді^[1]

a^{\frac{p - 1}{2}} \equiv {\begin{matrix} 1 (\mod p) & \exists x, a \equiv x^{2} (\mod p) \\ - 1 (\mod p) & ∄ x \end{matrix}

Критерій Ейлера можна стисло сформулювати використовуючи символ Лежандра:^[2]

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

Критерій вперше з'явився в документі Ейлера 1748 року.^[3]

Доведення

Доведення використовує факт того, що класи лишків по простому модулю є полями. Також існує (p − 1)/2 квадратичних лишків і така сама кількість нелишків (mod p).

Мала теорема Ферма каже, що

a^{p - 1} \equiv 1 (\mod p)

(Припустимо, що a на є 0 mod p). Це можна записати як

(a^{\frac{p - 1}{2}} - 1) (a^{\frac{p - 1}{2}} + 1) \equiv 0 (\mod p) .

Оскільки цілі mod p утворюють поле, якийсь з цих множників повинен бути конгруентним нулю.

Тут припустимо, що a є квадратичним лишком, a ≡ x²,

a^{\frac{p - 1}{2}} \equiv {x^{2}}^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1 (\mod p) .

Отже, кожен квадратичний лишок (mod p) робить перший множник нулем.

Теорема Лагранжа говорить, що існує не більше ніж (p − 1)/2 значень a, які обнуляють перший множник. Але також відомо, що наявні (p − 1)/2 різних квадратичних лишків (mod p) (окрім 0). Отже, вони і є класами лишків, які роблять перший множник нулем. Інші (p − 1)/2 класів лишків, нелишкі, повинні бути такими, що обнуляють другий множник.