【徹底解説】オイラーの定理

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

オイラーの定理

互いに素な正の整数$a$,$m$に対し,以下が成り立つ。

\begin{align}
a^{\varphi(m)}\equiv 1\pmod{m}
\end{align}

ただし,$\varphi(m)$はオイラー関数とする。

オイラーの定理はフェルマーの小定理の一般化となっています。

証明

オイラー関数の定義より,$m$と互いに素な数は$\varphi(m)$個存在します。そこで,

\begin{align}
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$となることが示されます。仮に,

\begin{align}
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$の要素を全て乗じた値は合同で,

\begin{alignat}{2}
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)}$で割ることができ,

\begin{align}
1\equiv a^{\varphi(m)}\pmod{m}
\end{align}

が成り立ちます。以上より,オイラーの定理が示されました。

シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次