本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
オイラーの定理
オイラーの定理はフェルマーの小定理の一般化となっています。
証明
オイラー関数の定義より，$m$と互いに素な数は$\varphi(m)$個存在します。そこで，
P &= \left\{x_{1},x_{2},\ldots,x_{\varphi(m)}\right\} \in \left\{1,2,\ldots,m\right\}
\end{align}
とおきます。いま，$P$の各要素に$a$を乗じた集合を$Q$とすると，$m$を法として$P\equiv Q$となります。このことを証明します。$a$は$m$と互いに素であることから，$ax_{1},\ldots,ax_{\varphi(m)}$は$P$の要素となりますので，これらが全て異なることを示すことができれば，$m$を法として$P\equiv Q$となることが示されます。仮に，
ax_{i}\equiv ax_{j}\pmod{m}\label{仮定}
\end{align}
となる$i$，$j$が存在したとすると，$a$と$m$は互いに素ですので，合同式の性質より式($\ref{仮定}$)の両辺を$a$で割ることができ，$x_{i}\equiv x_{j}$となります。これは，$m$と互いに素な数は$\varphi(m)$個存在するという$P$の定義に矛盾します。したがって，$m$を法として$P\equiv Q$となることが示されました。このことから，$P$の要素と$Q$の要素を全て乗じた値は合同で，つぎが成り立ちます。
x_{1}x_{2}\cdots x_{\varphi(m)}&\equiv ax_{1}ax_{2}\cdots ax_{\varphi(m)}&&\pmod{m}\\[0.7em]
&\equiv a^{\varphi(m)}x_{1}x_{2}\cdots x_{\varphi(m)}&&\pmod{m}\label{補題の結果}
\end{alignat}
互いに素な整数の性質から，$m$と互いに素な数の積は$m$と互いに素となりますので，$x_{1}\cdots x_{\varphi(m)}$は$m$と互いに素となります。合同式の性質より，式($\ref{補題の結果}$)の両辺を$x_{1}\cdots x_{\varphi(m)}$で割ることができ，
1\equiv a^{\varphi(m)}\pmod{m}
\end{align}
が成り立ちます。以上より，オイラーの定理が示されました。
参考文献
本稿の執筆にあたり参考にした文献は，以下でリストアップしております。
コメント