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

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

Калі $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}}$. ■

Гл. таксама

• Функцыя Эйлера
• Малая тэарэма Ферма