З Вікіпедыі, свабоднай энцыклапедыі
Тэарэма Эйлера ў тэорыі лікаў абвяшчае:
Частковым выпадкам тэарэмы Эйлера з'яўляецца малая тэарэма Ферма (пры простым m ). У сваю чаргу, тэарэма Эйлера з'яўляецца следствам тэарэмы Лагранжа.
Хай
x
1
,
…
,
x
φ
(
m
)
{\displaystyle x_{1},\dots ,x_{\varphi (m)}}
— усе розныя натуральныя лікі, меншыя
m
{\displaystyle m}
і ўзаемна простыя з ім.
Разгледзім усе магчымыя здабыткі
x
i
a
{\displaystyle x_{i}a}
для ўсіх
i
{\displaystyle i}
ад
1
{\displaystyle 1}
да
φ
(
m
)
{\displaystyle \varphi (m)}
Паколькі
a
{\displaystyle a}
ўзаемна просты з
m
{\displaystyle m}
і
x
i
{\displaystyle x_{i}}
ўзаемна просты з
m
{\displaystyle m}
, то і
x
i
a
{\displaystyle x_{i}a}
таксама ўзаемна просты з
m
{\displaystyle m}
, г. зн.
x
i
a
≡
x
j
(
mod
m
)
{\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}}
для некаторага
j
{\displaystyle j}
.
Адзначым, што ўсе астачы
x
i
a
{\displaystyle x_{i}a}
пры дзяленні на
m
{\displaystyle m}
розныя. Сапраўды, хай гэта не так, то існуюць такія
i
1
≠
i
2
{\displaystyle i_{1}\neq i_{2}}
, што
x
i
1
a
≡
x
i
2
a
(
mod
m
)
{\displaystyle x_{i_{1}}a\equiv x_{i_{2}}a{\pmod {m}}}
або
(
x
i
1
−
x
i
2
)
a
≡
0
(
mod
m
)
.
{\displaystyle (x_{i_{1}}-x_{i_{2}})a\equiv 0{\pmod {m}}.}
Так як
a
{\displaystyle a}
ўзаемна просты з
m
{\displaystyle m}
, то апошняе роўнасць раўнасільная таму , што
x
i
1
−
x
i
2
≡
0
(
mod
m
)
{\displaystyle x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}}
или
x
i
1
≡
x
i
2
(
mod
m
)
{\displaystyle x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}}
.
Гэта супярэчыць таму, што лікі
x
1
,
…
,
x
φ
(
m
)
{\displaystyle x_{1},\dots ,x_{\varphi (m)}}
парамі розныя па модулю
m
{\displaystyle m}
.
Перамножым ўсе параўнанні выгляду
x
i
a
≡
x
j
(
mod
m
)
{\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}}
. Атрымаем:
x
1
⋯
x
φ
(
m
)
a
φ
(
m
)
≡
x
1
⋯
x
φ
(
m
)
(
mod
m
)
{\displaystyle x_{1}\cdots x_{\varphi (m)}a^{\varphi (m)}\equiv x_{1}\cdots x_{\varphi (m)}{\pmod {m}}}
або
x
1
⋯
x
φ
(
m
)
(
a
φ
(
m
)
−
1
)
≡
0
(
mod
m
)
{\displaystyle x_{1}\cdots x_{\varphi (m)}(a^{\varphi (m)}-1)\equiv 0{\pmod {m}}}
.
Паколькі лік
x
1
⋯
x
φ
(
m
)
{\displaystyle x_{1}\cdots x_{\varphi (m)}}
ўзаемна просты з
m
{\displaystyle m}
, то апошняе параўнанне раўнасільнае таму, што
a
φ
(
m
)
−
1
≡
0
(
mod
m
)
{\displaystyle a^{\varphi (m)}-1\equiv 0{\pmod {m}}}
или
a
φ
(
m
)
≡
1
(
mod
m
)
.
{\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}.}
■
Разгледзім мультыплікатыўную групу
Z
n
∗
{\displaystyle \mathbb {Z} _{n}^{*}}
абаротных элементаў колцы вылікаў
Z
n
{\displaystyle \mathbb {Z} _{n}}
. Яе парадак роўны
φ
(
n
)
{\displaystyle \varphi (n)}
паводле вызначэння функцыі Эйлера. Паколькі лік
a
{\displaystyle a}
ўзаемна просты з
n
{\displaystyle n}
, элемент
a
¯
{\displaystyle {\overline {a}}}
у
Z
n
{\displaystyle \mathbb {Z} _{n}}
, які адпавядае яму, з'яўляецца абаротным і належыць
Z
n
∗
{\displaystyle \mathbb {Z} _{n}^{*}}
. Элемент
a
¯
∈
Z
n
∗
{\displaystyle {\overline {a}}\in \mathbb {Z} _{n}^{*}}
спараджае цыклічную падгрупу, парадак якой, згодна з тэарэме Лагранжа, дзеліць
φ
(
n
)
{\displaystyle \varphi (n)}
, адсюль
a
¯
φ
(
n
)
=
1
¯
{\displaystyle {\overline {a}}^{\varphi (n)}={\overline {1}}}
. ■