З дапамогай тэорыі лікаў
правіць
Хай
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}}}
