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

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

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

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}}

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

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

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

Доведення

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

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

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

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

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

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

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

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 класів лишків, нелишкі, повинні бути такими, що обнуляють другий множник.

Примітки

Gauss, DA, Art. 106
Hardy & Wright, thm. 83
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 0-387-96254-9.

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 0-8284-0191-8.

Hardy, G. H.; Wright, E. M. (1980). An Introduction to the Theory of Numbers (Fifth edition). Oxford: Oxford University Press. ISBN 978-0-19-853171-5.

Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. ISBN 3-540-66957-4.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Gauss, DA, Art. 106

[2] Hardy & Wright, thm. 83

[3] Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive