オイラーの定理

2017年07月03日(月)  List  Edit  New

命題
整数$n$が整数$m > 1$と互いに素であるならば、
$$n^{\varphi(m)}\equiv1\pmod m$$
が成り立つ。
証明
$m$と互いに素である$m$未満の正整数全体の集合を$$X = \{ x_1,x_2,\ldots,x_{\varphi(m)}\}$$とする。また集合$X_n$を、
$$
X_n = \{xn \bmod m \,|\,x \in X \}
$$
とおくと、$X_n = X$が成り立つ(※1)。よって$X_n$の要素をすべて乗じた結果と、$X$の要素をすべて乗じた結果は等しい。
$$
x_1\cdot x_2\cdots x_{\varphi(m)} = (x_1n \bmod m)\cdot(x_2n \bmod m)\cdots (x_{\varphi(m)}n \bmod m)
$$
これから、
$$x_1\cdot x_2\cdots x_{\varphi(m)}\equiv x_1n\cdot x_2n\cdots x_{\varphi(m)}n \pmod m$$
が成り立つ。式を整理して、
$$n^{\varphi(m)}\prod_{x \in X}x \equiv \prod_{x \in X}x \pmod m$$
$\prod\limits_{x \in X}x$は$m$と互いに素なので、
$$n^{\varphi(m)} \equiv 1 \pmod m$$
が示された。(証明終わり)

※1
https://story.hyuki.net/20170703002408/

※メモ
$m > 1$と入れたのは$m = 1$のときの取り扱いを(フェルマーの小定理との関係で)整理したいから。あとで考える。