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

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

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

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&\exists x,a\equiv x^{2}{\pmod {p}}\\-1{\pmod {p}}&\nexists x\end{cases}}}$

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

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}.}$

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

Доведення

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

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

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

${\displaystyle (a^{\tfrac {p-1}{2}}-1)(a^{\tfrac {p-1}{2}}+1)\equiv 0{\pmod {p}}.}$

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

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

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {x^{2}}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}$

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

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

Примітки

1. Gauss, DA, Art. 106
2. Hardy & Wright, thm. 83
3. Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 

• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 

• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 

• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN