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

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

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

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

Доказы

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

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

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

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

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

$x_{i_1}a\equiv x_{i_2}a(\mathrm{mod}m)$

або

$(x_{i_1}-x_{i_2})a\equiv 0(\mathrm{mod}m).$

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

$x_{i_1}-x_{i_2}\equiv 0(\mathrm{mod}m)$ или $x_{i_1}\equiv x_{i_2}(\mathrm{mod}m)$.

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

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

$x_1\cdots x_{\phi (m)}{a}^{\phi (m)}\equiv x_1\cdots x_{\phi (m)}(\mathrm{mod}m)$

або

$x_1\cdots x_{\phi (m)}(a^{\phi (m)}-1)\equiv 0(\mathrm{mod}m)$.

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

$a^{\phi (m)}-1\equiv 0(\mathrm{mod}m)$

или

$a^{\phi (m)}\equiv 1(\mathrm{mod}m).$ ■

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

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

Гл. таксама

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