У теорії чисел критерій Ейлера — це формула для визначення чи є ціле квадратичним лишком по простому модулю. А саме,
Нехай p буде непарним простим і a буде цілим числом взаємно простим з p. ТодіGauss, DA, Art. 106
Критерій Ейлера можна стисло сформулювати використовуючи символ Лежандра:Hardy & Wright, thm. 83
Критерій вперше з'явився в документі Ейлера 1748 року.Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
Доведення
Доведення використовує факт того, що класи лишків по простому модулю є полями. Також існує (p − 1)/2 квадратичних лишків і така сама кількість нелишків (mod p).
Мала теорема Ферма каже, що
(Припустимо, що a на є 0 mod p). Це можна записати як
Оскільки цілі mod p утворюють поле, якийсь з цих множників повинен бути конгруентним нулю.
Тут припустимо, що a є квадратичним лишком, a ≡ x2,
Отже, кожен квадратичний лишок (mod p) робить перший множник нулем.
Теорема Лагранжа говорить, що існує не більше ніж (p − 1)/2 значень a, які обнуляють перший множник. Але також відомо, що наявні (p − 1)/2 різних квадратичних лишків (mod p) (окрім 0). Отже, вони і є класами лишків, які роблять перший множник нулем. Інші (p − 1)/2 класів лишків, нелишкі, повинні бути такими, що обнуляють другий множник.
Примітки