Тэарэма Эйлера (тэорыя лікаў)

Тэарэма Эйлера ў тэорыі лікаў абвяшчае:

Калі $a$ і $m$ узаемна простыя, то $a^{\varphi (m)}\equiv 1{\pmod {m}}$ , дзе $\varphi (m)$ — функцыя Эйлера.

Частковым выпадкам тэарэмы Эйлера з'яўляецца малая тэарэма Ферма (пры простым m). У сваю чаргу, тэарэма Эйлера з'яўляецца следствам тэарэмы Лагранжа.

Доказы

З дапамогай тэорыі лікаў

Хай $x_{1},\dots ,x_{\varphi (m)}$ — усе розныя натуральныя лікі, меншыя $m$ і ўзаемна простыя з ім.

Разгледзім усе магчымыя здабыткі $x_{i}a$ для ўсіх $i$ ад $1$ да $\varphi (m)$

Паколькі $a$ ўзаемна просты з $m$ і $x_{i}$ ўзаемна просты з $m$ , то і $x_{i}a$ таксама ўзаемна просты з $m$ , г. зн. $x_{i}a\equiv x_{j}{\pmod {m}}$ для некаторага $j$ .

Адзначым, што ўсе астачы $x_{i}a$ пры дзяленні на $m$ розныя. Сапраўды, хай гэта не так, то існуюць такія $i_{1}\neq i_{2}$ , што

x_{i_{1}}a\equiv x_{i_{2}}a{\pmod {m}}

або

(x_{i_{1}}-x_{i_{2}})a\equiv 0{\pmod {m}}.

Так як $a$ ўзаемна просты з $m$ , то апошняе роўнасць раўнасільная таму , што

x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}

или

x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}

.

Гэта супярэчыць таму, што лікі $x_{1},\dots ,x_{\varphi (m)}$ парамі розныя па модулю $m$ .

Перамножым ўсе параўнанні выгляду $x_{i}a\equiv x_{j}{\pmod {m}}$ . Атрымаем:

x_{1}\cdots x_{\varphi (m)}a^{\varphi (m)}\equiv x_{1}\cdots x_{\varphi (m)}{\pmod {m}}

або

x_{1}\cdots x_{\varphi (m)}(a^{\varphi (m)}-1)\equiv 0{\pmod {m}}

.

Паколькі лік $x_{1}\cdots x_{\varphi (m)}$ ўзаемна просты з $m$ , то апошняе параўнанне раўнасільнае таму, што

a^{\varphi (m)}-1\equiv 0{\pmod {m}}

или

a^{\varphi (m)}\equiv 1{\pmod {m}}.

■

З дапамогай тэорыі груп

Разгледзім мультыплікатыўную групу $\mathbb {Z} _{n}^{*}$ абаротных элементаў колцы вылікаў $\mathbb {Z} _{n}$ . Яе парадак роўны $\varphi (n)$ паводле вызначэння функцыі Эйлера. Паколькі лік $a$ ўзаемна просты з $n$ , элемент ${\overline {a}}$ у $\mathbb {Z} _{n}$ , які адпавядае яму, з'яўляецца абаротным і належыць $\mathbb {Z} _{n}^{*}$ . Элемент ${\overline {a}}\in \mathbb {Z} _{n}^{*}$ спараджае цыклічную падгрупу, парадак якой, згодна з тэарэме Лагранжа, дзеліць $\varphi (n)$ , адсюль ${\overline {a}}^{\varphi (n)}={\overline {1}}$ . ■

Гл. таксама