フェルマーの小定理

テンプレート:混同数論において、フェルマーの小定理（フェルマーのしょうていり、Fermat's little theorem）は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。

概要

p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、

a^p−1 ≡ 1 (mod p)

すなわち、a の p − 1 乗を p で割った余りは 1 であるというもの。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。

この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。

証明

証明(1)

二項定理から、数学的帰納法を用いて証明する方法が簡便である。元の定理は

a^p ≡ a (mod p)

と同値である（a と p は互いに素より、両辺を a で割れるから）。この形の命題として証明する。

補題：「(m + 1)^p を p で割った余りは m^p + 1 を p で割った余りに等しい。」

（補題の証明）

(m + 1)^p = m^p + _pC₁m^p−1 + _pC₂m^p−2 + … + _pC_p−1m + 1 （二項定理）

右辺の両端以外の二項係数 _pC_k は全て p の倍数である。なぜなら、

<math>{}_p \text{C}_k = \frac{p(p-1)\cdots (p-k+1)}{k(k-1)\cdots 1}</math>

であり、p は素数で、k < p より、分子に含まれる p は約分されることはないからである。

故に、(m + 1)^p を p で割った余りは、両端の項 m^p + 1 を p で割った余りに等しい。（補題の証明終）

「a^p ≡ a (mod p)」を a に関する数学的帰納法で証明する。

補題に m = 1 を代入すると、2^p = (1 + 1)^p を p で割った余りは 1^p + 1 = 2 となり、a = 2 のとき成り立つ。

a = k のとき成り立つと仮定する。

補題より、(k + 1)^p を p で割った余りは k^p + 1 を p で割った余りに等しい。帰納法の仮定により k^p を p で割った余りは k を p で割った余りに等しいから、これは k + 1 を p で割った余りに等しい。

故に a = k + 1 のときも成り立つ。

ゆえに帰納法により a ≧ 2 に対して成り立つが、a = 0, 1 のときも、代入してみると明らかに成り立つ。

（証明終）

証明(2)

上の補題と同様に、(x + y)^p ≡ x^p + y^p (mod p) が示せる。これより、
a^p = {1 + (1 + 1 + … + 1)}^p
　　≡ 1^p + {1 + (1 + 1 + … + 1)}^p
　　≡ …
　　≡ 1^p + 1^p + … + 1^p
　　≡ a (mod p)
ここで a と p は互いに素なので、両辺を a で割ることができ、
a^p−1 ≡ 1 (mod p)
となる。（証明終）

オイラーの定理

テンプレート:Main 後になってレオンハルト・オイラーはこの定理を拡張し、a を n と互いに素な整数とすると、

a^φ(n) ≡ 1 (mod n)

が成り立つことを示した。ここで、φ(n) は n 未満の n と互いに素な自然数の個数を表し、オイラー関数 と呼ばれる。

特に n が素数のときは、φ(n) = n − 1 より、フェルマーの小定理に一致する。

カーマイケルの定理

m = φ(n) とすれば、a^m ≡ 1 (mod n) が n と互いに素な全ての a に対して成り立つが、φ(n) はこの性質を満たす m の最小の数とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、最小の m を与える。

テンプレート:仮リンク λ(n) を以下のように再帰的に定義する。

n = 2^e なら、

<math>\lambda (2^e )=\begin{cases}

1 &(e=1)\\ 2 &(e=2)\\ 2^{e-2} &(e \ge 3) \end{cases}</math> n が奇素数 p を用いて n = p^e と書けるなら、

λ(p^e) = p^e−1(p−1)

n が p₁^e₁ ... p_k^e_k と素因数分解できるなら、

λ(p₁^e₁ ... p_k^e_k) = lcm(λ(p₁^e₁), ... ,λ(p_k^e_k))

ここで lcm は最小公倍数。

カーマイケルの定理は、a と n が互いに素なとき、 a^λ(n) ≡ 1 (mod n) が成り立つという定理である。

λ(n) が n − 1 の約数であるとき、n はカーマイケル数と呼ばれ、自身と互いに素であるような全ての底でフェルマーテストを通過する絶対擬素数となる。

フェルマーテスト

フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。

フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。

対偶

n と互いに素な整数 a が

<math>a^{n-1} \not\equiv 1\pmod{n}</math>

を満たせば、n は合成数である。

この十分条件を用いて、次のように自然数 n の素数判定を行う。

パラメータとして、2 以上 n 未満の自然数 a を1つ定める。
a と n が互いに素でなければ「n は合成数」と出力して終了。
<math>a^{n-1} \not\equiv 1\pmod{n}</math> ならば「n は合成数」と出力して終了する。そうでないとき「n は確率的素数」と出力して終了する。

フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。

疑わしければ、「確率的素数」と出力された場合にはまた異なる a を用いて再びテストを行う。十分な回数だけ a を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。

しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにも拘らず、ほとんどいかなる a を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。

フェルマーテストを改善するアルゴリズムとしては、ラビン-ミラー素数判定法やAKS素数判定法がある。

一般化

フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。G を位数 m の有限群とすると、G の任意の元 g に対して g^m は単位元に一致する。オイラーの定理は G が乗法群 (Z/nZ)^× のときの場合であり、フェルマーの小定理はさらに n が素数の場合である。

参考文献

外部リンク