オイラーの定理とフェルマーの小定理

ここまでの議論は

を参照してください。

オイラーの定理

$\mathbb{Z}/n\mathbb{Z}$ で $n$ と互いに素な $a \in \mathbb{Z}$ を一つ取る。このとき $\overline{a}$ に自分自身を繰り返しかけると $\overline{a}$ は零因子ではないため、いつかは $\overline{1}$ になる。仮に $\overline{1}$ にならなかったとすると、べき乗したときの値の候補は有限であるため $\overline{a}^k = \overline{a}^l$ となる $k, l \in \mathbb{Z}$ が存在する。仮定より $\overline{a}$ の逆元が存在するので、両辺に $\overline{a}^{-1}$ を $l$ 回かけて $\overline{a}^{k - l} = \overline{1}$ となる。

このように $\overline{a}^k = \overline{1}$ となる $k$ を $\overline{a}$ の位数という。

$1$ 以上 $n$ 以下の整数で $n$ と互いに素なものの個数を表す関数

$$\varphi\left(n\right) = \#\left\{ m \in \mathbb{N} | 1 \le m \le n, \gcd(m, n) = 1 \right\}$$

をオイラー関数という。

$n$ と互いに素な $a \in \mathbb{Z}$ に対して

$$a^{\varphi\left(n\right)} \equiv 1 \mod(n)$$

となり、これをオイラーの定理という。

オイラー関数について

$p$ が素数のとき $\varphi\left(p\right) = p - 1$
$p^m$ で $p$ が素数のとき $\varphi\left(p^m\right) = p^n - p^{n-1} = p^n (1 - 1/p)$
$l, m$ が互いに素のとき $\varphi\left(lm\right) = \varphi\left(l\right)\varphi\left(m\right)$

が成り立つ。したがって $n$ を割り切るすべての素数を $\left\{p_1, p_2, \ldots, p_m\right\}$ とすると

$$\varphi\left(n\right) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\dots\left(1 - \frac{1}{p_m}\right)$$

となる。

例 $n = 15$

$n = 15$ とすると $15 = 3 \times 5$ より $\varphi\left(15\right) = (3 - 1)(5 - 1) = 8$ となる。実際に

$$2^8 = 256 = 17 \times 15 + 1 \equiv 1 \mod(15)$$

となる。

フェルマーの小定理

$n = p$ が素数の場合のオイラーの定理

$$a^{\varphi\left(p\right)} = a^{p - 1} \equiv 1 \mod(p)$$

をフェルマーの小定理という。

フェルマーの小定理の対偶は大きな数の素数判定に利用され、フェルマーテストと言われる。

$n \in \mathbb{N}$ が素数かどうか判定したい場合に以下の手順で確率的に素数の可能性が高い数を判定できる。

$2 \le a < n, a \in \mathbb{N}$ を一つ選ぶ
$\gcd(a, n) \ne 1$ であれば $n$ は合成数となり終了
$a ^ {n - 1} \not\equiv 1 \mod(n)$ であれば $n$ は合成数となり終了

上記の手順を繰り返しパスし続けることで素数の可能性が高まる。このテストは例えば RSA 暗号で大きな素数を生成する際に利用されることがある。

カーマイケルの定理

フェルマーテストにすべて通過する、つまり $n$ と互いに素な $n$ 以下の任意の自然数 $a$ に対して

$$a ^ {n - 1} \equiv 1 \mod(n)$$

となる自然数が存在するとき、この $n$ をカーマイケル数という。カーマイケル数は $561, 1105, 1729, \ldots$ と無数に存在することが知られている。

さて、ここでオイラーの定理の例の $n = 15$ に戻ろう。少し計算してみると

$2^2 = 4$
$2^3 = 8$
$2^4 = 16 \equiv 1 \mod(15)$

と $\varphi\left(15\right) = 8$ よりも小さい指数でべき乗すると $1$ になるものが見つかった。オイラーの定理を改良し最小の指数を求める方法が知られている。

ここでカーマイケル関数 $\lambda(n)$ を下記のように定義する。

$n = 2^m$ の場合は

$m = 1$ のときは $\lambda(2^m) = 1$
$m = 2$ のときは $\lambda(2^m) = 2$
$m > 2$ のときは $\lambda(2^m) = 2^{m - 2}$

と定義する。

$n$ が奇素数 $p$ に対して $n = p^m$ と書けるなら

$$\lambda(p^m) = p^{m-1} (p - 1)$$

と定義する。

$n = {p_1}^{m_1} {p_2}^{m_2} \dots {p_k}^{m_k}$ と素因数分解されるなら

$$\lambda({p_1}^{m_1} {p_2}^{m_2} \dots {p_k}^{m_k}) = lcm \left\{\lambda\left({p_1}^{m_1}\right), \lambda\left({p_2}^{m_2}\right), \ldots, \lambda\left({p_k}^{m_k}\right)\right\}$$

と定義する。ここで lcm は最小公倍数とする。このとき $n$ と互いに素な $a$ に対して

$$a ^ {\lambda(n)} \equiv 1 \mod(n)$$

が成り立ち $\lambda(n)$ が最小の数となる。これをカーマイケルの定理という。

実際に $n = 15$ に対して

$$\lambda(15) = lcm \left\{\lambda(3), \lambda(5)\right\} = lcm \left\{(3 - 1), (5 - 1) \right\} = 4$$

となる。

なお $\lambda(n)$ が $n - 1$ の約数であるとき $n$ はカーマイケル数となる。

まとめ

$n$ と互いに素な自然数 $a$ に対して、べき乗すると $n$ を法として $1$ と合同になる指数を具体的に求めるいくつかの方法を紹介しました。

オイラーの定理で $n$ が素数の場合はフェルマーの小定理と呼ばれていること (歴史的にはフェルマーの小定理をオイラーが一般の場合に拡張した) と、オイラー関数を改良して最小の値を与えるカーマイケル関数を紹介しました。

フェルマーの小定理は素数判定に利用される (フェルマーテスト) ことと、フェルマーテストをすべてすり抜ける擬素数がカーマイケル数と呼ばれていることを紹介しました。

オイラーの定理とフェルマーの小定理