Fermatの小定理とEulerの定理
Fermatの小定理
Fermatの小定理は、合同式と素数との関係において、とくに重要な定理であり、さまざまな素数判定法の基礎になっている。ここではFermatの小定理の一般化であるEulerの定理とあわせて解説する。
$p$ が素数で $a$ が $p$ で割り切れない整数のとき
$$a^{p-1}\equiv 1\Mod{p}$$
が成り立つ。
前ページの定理5
の証明2のように $am$ を $p$ で割った余りを $s_m (i=0, 1, \ldots, p-1)$ とすると $s_0, s_1, \ldots, s_{p-1}$ は $0, 1, \ldots, p-1$ をすべてとらなければならず、かつ $i\neq j$ のとき $s_i\neq s_j$ である。
$s_0=0$ であるから、$s_1, s_2, \ldots, s_{p-1}$ は $1, \ldots, p-1$ のそれぞれの値を$1$回ずつとる。よって
$$a^{p-1} (p-1)!\equiv \prod_{m=1}^{p-1} (am)\equiv \prod_{m=1}^{p-1} s_m\equiv (p-1)!\Mod{p}$$
が成り立つ。
$1, 2, \ldots, p-1$ は $p$ で割り切れないから $(p-1)!$ も $p$ で割り切れない。よって
前ページの定理4
より
$$a^{p-1}\equiv 1\Mod{p}$$
が成り立つ。
とくに、$p$ が奇素数ならば、つねに
$$2^{p-1}\equiv 1\Mod{p}$$
が成り立つ。
しかし、
$$2^{340}\equiv (2^{10})^{34}\equiv 1\Mod{341}$$
のように、$2^{N-1}\equiv 1\Mod{N}$ となるからといって、$N$ が素数であるとは限らない。
したがって、Fermatの小定理はそのままでは、与えられた整数が素数かどうかを確かめることには使用できない。
Eulerの定理
$\varphi(N)$ を $N$ より小さい正の整数 $1, 2, \ldots N-1$ のうち、$N$ と互に素であるものの個数とする。
このとき、次の事実が成り立つ。
$a$ が $N$ と互に素な整数ならば $a^{\varphi(N)}\equiv 1\Mod{p}$.
$1, 2, \ldots , N-1$ のなかで $N$ と互に素な整数全体を $s_1, s_2, \ldots, s_{\varphi(N)}$ とし、$as_i$ を $N$ で割った余りを $t_i$ とおく。
倍数と約数: 命題4
より各 $t_i$ も $N$ と互に素である。また、
前ページの定理4
より各 $t_i$ は相異なる値をとらなければならない。
よって $t_1, t_2, \ldots, t_{\varphi(N)}$ は $1, 2, \ldots , N-1$ のなかで $N$ と互に素な整数を$1$回ずつとるから
$$\prod_i t_i=\prod_i s_i$$
となるので
$$a^{\varphi(N)}\prod_i s_i=\prod_i (as_i)\equiv \prod_i t_i=\prod_i s_i\Mod{N}$$
が成り立つ。
$s_i$ はいずれも $N$ と互に素だから再び
倍数と約数: 命題4
より $\prod_i s_i$ も $N$ と互に素なので
$$a^{\varphi(N)}\equiv 1\Mod{N}$$
が成り立つことがわかる。
$p$ が素数のとき $\varphi(p)=p-1$ だから、この定理はFermatの小定理の拡張となっている。
$\varphi(N)$ を Euler関数、Eulerの$\varphi$関数、Eulerのtotientなどと呼ぶ。一般の整数に対するEuler関数の値は後に 中国式剰余定理 を用いて求める。一方で $\varphi(N)=N-1 \Longleftrightarrow$ $N$ が素数であることはすぐにわかる。実際 $N$ が素数でなければ $2, \ldots, N-1$ のなかに $N$ の約数 $d$ が存在し、$\gcd(d, N)=d>1$ となるから $\varphi(N)< N-1$ となる。
この議論はそのままでは、与えられた数が素数かどうかの判定に利用するのは実用的ではない。しかし、合同式に関するより深い考察から、合同式を用いて与えられた数が素数かどうかをより速く判定する方法が知られている。詳しくは後の章の 合同式に基づく古典的な素数判定法 の節を参照。
参考文献
