次: 循環小数 上: フェルマの小定理 前: フェルマの小定理

フェルマの小定理

定理 23 (オイラーの定理)
     $m$ を正整数とし $a$ を $m$ と互いに素な整数とする． このとき

$$a^{\varphi(m)}\equiv 1\quad (\bmod.\ m)$$ (2.29)

が成り立つ．

とくに $m=p\ (素数)$ に対しては, $(a,\ p)=1$ のとき

$$a^{p-1}\equiv 1\quad (\bmod.\ p)$$ (2.30)

が成り立つ．こちらの方をフェルマの小定理という．■

証明     $m$ を法とする既約類の個数は$\varphi(m)$個ある．その一組を

$$x_1,\ x_2,\ \cdots,\ x_{\varphi(m)}$$

とする．このとき

$$ax_1,\ ax_2,\ \cdots,\ ax_{\varphi(m)}$$

もまた一組の既約剰余系である． なぜなら $(a,\ m)=1$ より

$$x\equiv y\quad (\bmod.\ m)\quad \iff\quad ax\equiv ay\quad (\bmod.\ m)$$

であるから $x$ が剰余系なら $ax$ も剰余系である． つまり $x$ と $m$ を法として合同な整数の集合とすれば，その集合の元にすべて $a$ を乗じた 整数の集合は確かに $ax$ と合同な整数の全体になっており, $ax$ も剰余系である． さらに $x$ が $m$ と互いに素なら $ax$ も $m$ と互いに素なので，既約剰余系からは 既約剰余系が得られることもわかる．

したがって二つの数の集合

$$\{x_1,\ x_2,\ \cdots,\ x_{\varphi(m)}\}\quad と \quad \{ax_1,\ ax_2,\ \cdots,\ ax_{\varphi(m)}\}$$

の各元は $m$ を法として互いに合同なものが一対一に対応している．

よって，その積は$m$ を法として互いに合同である．つまり

$$\begin{eqnarray*} x_1x_2\cdots x_{\varphi(m)} &\equiv &ax_1ax_2\cdots ax_{\var... ...uiv &a^{\varphi(m)}x_1x_2\cdots x_{\varphi(m)}\quad (\bmod.\ m) \end{eqnarray*}$$

$(x_1x_2\cdots x_{\varphi(m)},\ m)=1$ であるから

$$a^{\varphi(m)}\equiv 1\quad (\bmod.\ m)$$

である．オイラーの定理(2.29)が示された．

$m=p$ なら $\varphi(p)=p-1$ であるから， オイラーの定理の特別な場合としてフェルマの小定理(2.30)が成り立つ．□

例 2.4.1  

$$\begin{array}{lll} \varphi(5)=4&13^4\equiv 1\quad (\bmod.... ...-1=(7-1)(7+1)\\ &&\times(7^2+1)(7^4+1)(7^8+1) \end{array}$$

上の例で13の場合は4乗して初めて $1\quad (\bmod.\ 5)$ となるが， 11の場合は2乗した段階ですでに $1\quad (\bmod.\ 5)$ である．

$a$ のべきの中で $a^e\equiv 1\quad (\bmod.\ m)$ となる最小の $e$ を $a$ の法 $m$ に関する指数という．

定理 24
     $a$ の法 $m$ に関する指数を $e$ とする． このとき $a^k\equiv 1\quad (\bmod.\ m)$ となったとすれば $k$ は $e$ の倍数である． 特に $\varphi(m)$ は $e$ の倍数である．逆にいうと法 $m$ に関する指数となりうるのは $\varphi(m)$ の約数にかぎる．■

証明     $k$ を $e$ で割った商を $q$ ，余りを $r$ とする．

$$1\equiv a^k=a^{eq+r}\equiv a^r\quad (\bmod.\ m)$$

ここで $0\le r<e$ であるが，もし $r \ne 0$ なら $a^r\equiv 1\quad (\bmod.\ m)$ となる 正の整数 $r$ があることになり $e$ の最小性に反する．ゆえに $r=0$ ． つまり $k$ は $e$ の倍数である．□

次: 循環小数 上: フェルマの小定理 前: フェルマの小定理