既約剰余系

既約剰余系

 $m$ を法とする剰余系の1つを
 
\[\{\;1,\;2,\;\cdots,\;m-1\:\}\]
とします。この集合の要素の中から $m$ と互いに素であるものだけを集めた集合を $m$ を法とする 既約剰余系 (irreducible residue system) といいます。オイラーの関数 $\varphi(m)$ は既約剰余系の要素の個数であるともいえます。

オイラーの定理

 $9$ を法とする既約剰余系をつくってみると
 
\[\{\;1,\;2,\;4,\;5,\;7,\;8\:\}\]
となります。この中の要素を $k$ として
 
\[a^k\equiv x\quad (\mathrm{mod}\:m)\]
なる $x$ を表に並べてみます。

Excel mod9 べき乗(オイラーの定理)

 $k$ が $\varphi(9)=6$ のところだけきれいに $1$ が揃っていますね。
 すなわち $a^{\varphi(9)}\equiv 1\;(\mathrm{mod}\:9)$ が成り立っています。
 これは偶然ではないことが以下の定理でわかります。

[定理 D12 オイラーの定理]\[(a,\:m)=1\quad\Longrightarrow\quad a^{\varphi(m)}\equiv 1\quad (\mathrm{mod}\:m)\]

[定理 D12 の証明] $k=\varphi(m)$ とし、$m$ を法とする既約剰余系を
 
\[\{\;x_1,\;x_2,\;\cdots\;x_k\:\}\quad (1\leq x_i\leq m,\;i=1,\;2,\;\cdots,\;k)\]
とします。ここで
 
\[\{\;ax_1,\;ax_2,\;\cdots\;ax_k\:\}\quad (1\leq x_j\leq m,\;j=1,\;2,\;\cdots,\;k)\]
という集合をつくり、

$i\neq j$ かつ $ax_i\equiv ax_j\quad (\mathrm{mod}\:m),\quad (1\leq x_i\lt x_j\leq m)$

と仮定してみると
 
\[a(x_j-x_i)\equiv 0\quad (\mathrm{mod}\:m)\]
となります。$(a,\:m)=1$ なので
 
\[m\,|\,x_j-x_i\]
となるはずですが、これは $1\leq x_j-x_i\leq m-1$ という仮定に反するので不合理です。ゆえに
 
\[i\neq j\quad\Longrightarrow\quad ax_i\not\equiv ax_j\quad (\mathrm{mod}\:m)\]
となるので、集合
 
\[\{\;ax_1,\;ax_2,\;\cdots\;ax_k\:\}\quad (1\leq x_j\leq m,\;j=1,\;2,\;\cdots,\;k)\]
は既約剰余系であることになります。したがって
 
\[(ax_1)\,(ax_2)\,\cdots(ax_k)\,\equiv\, x_1\,x_2\,\cdots x_k\quad (\mathrm{mod}\:m)\]
という合同式が成り立つので
 
\[(a^k-1)\, x_1\,x_2\,\cdots x_k\,\equiv\,0\quad (\mathrm{mod}\:m)\]
 ここで $(x_i,\:m)=1$ より
 
\[a^k-1\equiv 0\quad (\mathrm{mod}\:m)\]
 すなわち
 
\[a^{\varphi(m)}\equiv 1\quad (\mathrm{mod}\:m)\]
が成り立ちます。(証明終)

 法 $9$ であれば $\varphi(9)=6$ なので、計算しなくても表にあるように
 
\[\begin{align*}1^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]2^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]4^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]5^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]7^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]8^6\equiv 1\quad (\mathrm{mod}\:9)\\[6pt]\end{align*}\]
が成り立つことがわかるということです。気になる人は関数電卓や Excel で計算してみてください。

エクセルや数学に関するコメントをお寄せください