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