既約剰余系

既約剰余系

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

オイラーの定理

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



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

[証明] $k=\phi (m)$ とし、$m$ を法とする既約剰余系を
$$\{x_1,x_2,\cdots x_k\}(1\le x_i\le m,i=1,2,\cdots ,k)$$
とします。ここで
$$\{a{x}_1,a{x}_2,\cdots a{x}_k\}(1\le x_j\le m,j=1,2,\cdots ,k)$$
という集合をつくり、

と仮定してみると
$$a(x_j-x_i)\equiv 0(\mathrm{mod}m)$$
となります。$(a,m)=1$ なので
$$m|x_j-x_i$$
となるはずですが、これは $1\le x_j-x_i\le m-1$ という仮定に反するので不合理です。ゆえに
$$i\ne j⟹a{x}_i\not\equiv a{x}_j(\mathrm{mod}m)$$
となるので、集合
$$\{a{x}_1,a{x}_2,\cdots a{x}_k\}(1\le x_j\le m,j=1,2,\cdots ,k)$$
は既約剰余系であることになります。したがって
$$(a{x}_1)(a{x}_2)\cdots (a{x}_k)\equiv x_1{x}_2\cdots x_k(\mathrm{mod}m)$$
という合同式が成り立つので
$$(a^k-1)x_1{x}_2\cdots x_k\equiv 0(\mathrm{mod}m)$$
ここで $(x_i,m)=1$ より
$$a^k-1\equiv 0(\mathrm{mod}m)$$
すなわち
$$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$$
が成り立ちます。（証明終）

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