フェルマーの小定理

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

概要

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

$a^{p-1} \equiv 1 \pmod{p}$

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

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

証明

証明①

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

$\forall a \in \mathbb{Z} ; a^{p} \equiv a \pmod{p}$

つまり「 a を p 乗したものを p で割ったあまり」は「 a を p で割ったあまりに等しい」という形の命題として証明する。

1. (m + 1)^p という式を展開することを考える。これは公式により、
   m^p + _pC₁m^p-1 + _pC₂m^p-2 + … + _pC_p-1m + 1
   となる。
2. ここで両端の項以外はすべての項に _pC_k が因数として含まれている。これは、p が素数であれば k が 1 以上 p 未満である限り必ず p で割り切れる。なぜなら _pC_k = p!/(p-k)!k! であり、p が素数であるなら分子には p が含まれているものの分母に p やその倍数は含まれないからである。
3. すると、両端の項以外は p で割り切れる。(m + 1)^p を p で割ったあまりは、残る m^p + 1 を p で割ったあまりと等しいことになる。
4. ここで、m = 1 とする。2^p = (1 + 1)^p を p で割ったあまりは 1^p + 1 = 2 ということになり、命題は a = 2 の場合に正しいことが証明された。
5. a に関する帰納法で示すために、a = k で命題が成立していると仮定する。ステップ3により、(k + 1)^p を p で割ったあまりは、k^p + 1 を p で割ったあまりに等しい。さらにこれは、帰納法の仮定により、k + 1 を p で割ったあまりに等しい。したがって命題は a = k + 1 でも成立する。数学的帰納法によって 2 以上のすべての a について命題は成立することになる。
6. a = 0, 1 の場合は命題の成立することが自明。

（証明終わり）

証明②

まず，２項定理の応用より，( 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 )
となる。　(Q.E.D.)

オイラーの定理

詳細は「オイラーの定理 (数論)」を参照

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

$a^{\varphi(n)} \equiv 1 \pmod{n}$

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

n が素数のときに限れば、$\varphi(n)=n-1$ であるからこれはフェルマーの小定理に一致する。

カーマイケルの定理

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

カーマイケル関数 λ(n) を以下のように再帰的に定義する。

n = 2^e なら、

$\lambda(2^e)=\begin{cases}1&\,:e=1\\2&\,:e=2\\2^{e-2}&\,:e\ge 3\end{cases}$

n が奇素数 p を用いて n = p^e と書けるなら、

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

n が $p_1{}^{e_1}\cdots p_k{}^{e_k}$ と素因数分解できるなら、

$\lambda(p_1{}^{e_1}\cdots p_k{}^{e_k})=\mathrm{lcm}(\lambda(p_1{}^{e_1}),\ldots,\lambda(p_k{}^{e_k}))$

ここで lcm は最小公倍数。

カーマイケルの定理は、a と n が互いに素なとき、

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

が成立する、という定理である。

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

フェルマーテスト

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

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

対偶

n と互いに素な 整数 a が

$a^{n-1} \ \not\equiv\ 1 \pmod{n}$

を満たせば、このとき n は合成数である。

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

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

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

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

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

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

一般化

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

参考文献

• 高木貞治『初等整数論講義〈第2版〉』共立出版、1971年、67頁、53-54頁。ISBN 4-320-01001-9
• G.H.ハーディ、E.M.ライト『数論入門Ⅰ』シュプリンガー・フェアラーク東京、2001年、82-107頁。ISBN 4-431-70848-0

外部リンク

• Weisstein, Eric W., "Fermat's Little Theorem" - MathWorld.（英語）
• Weisstein, Eric W., "Euler's Totient Theorem" - MathWorld.（英語）
• Weisstein, Eric W., "Carmichael's Theorem" - MathWorld.（英語）