フェルマーの小定理

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

概要

$p$ を素数とし、 $a$ を整数とすると、

$a^p\equiv a(\mathrm{mod}p)$

が成立すると言う定理である。また、 $p$ を素数とし、 $a$ を $p$ の倍数でない整数（ $a$ と $p$ は互いに素）とするときに、

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

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

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

証明

3通りの証明を示す。

証明(1)

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

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

（補題の証明）

$(m+1{)}^p=m^p+{}_p{\mathrm{C}}_1{m}^{p-1}+{}_p{\mathrm{C}}_2{m}^{p-2}+\cdots +{}_p{\mathrm{C}}_{p-1}m+1$（二項定理）

右辺の両端以外の二項係数 ${}_p{\mathrm{C}}_k$ はすべて $p$ の倍数である。なぜなら、

${}_p{\mathrm{C}}_k=\frac{p(p-1)\cdots (p-k+1)}{k(k-1)\cdots 1}$

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

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

命題「 $a^p\equiv a(\mathrm{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$ を $p$ で割った余りは $k+1$ を $p$ で割った余りに等しい。

したがって、命題は $a=k+1$ のときも成り立つ。

数学的帰納法によって、命題は $a\geqq 2$ に対して成り立つ。また、 $a=0,1$ のときは、代入してみると明らかに成り立つので、命題は $a\geqq 0$ に対して成り立つ。

（証明終）

証明(2)

上の補題と同様に、$(x+y{)}^p\equiv x^p+y^p(\mathrm{mod}p)$ が示せる。これより、

$\begin{array}{cc}{a}^p& =[1+(a-1){]}^p\\ & \equiv 1^p+[1+(a-2){]}^p\\ & \equiv 1+1^p+[1+(a-3){]}^p\\ & \equiv a(\mathrm{mod}p)\end{array}$

（証明終）

証明(3)

$p$ を素数とし、 $a$ と $p$ が互いに素とするときに、

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

が成立することを、ここで証明する。

集合 $\{1,2,3,\dots ,p-1\}$ は、全体として法 $p$ の下で $\{a,2a,3a,\dots ,(p-1)a\}$ と合同である。（背理法による証明）もし後者の集合内に

$ia\equiv ja(\mathrm{mod}p)$

となる $i,j$ (ただし、 $i\ne j$ )が存在したとする。すると、 $a$ と $p$ が互いに素なので、 $i\equiv j(\mathrm{mod}p)$ となり、 $0<i,j<p$ であることから、 $i=j$ となり、矛盾する。したがって、二つの集合は全体として合同であることが分かった。

それぞれの集合の要素をすべて掛け合わせると、

$(p-1)!\equiv (p-1)!a^{p-1}(\mathrm{mod}p)$

となる。 $p$ が素数であることから、 $p$ と $(p-1)!$ とは互いに素なので、

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

（証明終）

性質

フェルマーの小定理は、乱数を発生する用途に使われることがある。しかし、このような場合、あらゆる（p と互いに素な）a について、

$b=a^n(\mathrm{mod}p)$

が、$n=1..p-1$ に沿って

$1\le b<p$

の全要素を順繰りに巡ることを保証しているわけではない点には注意すべきである。実際、次の各表では、$n=p-1$ である右端の列が全てゼロになることは確かだが、それ以外にもゼロは出現している。

$p=3$ の場合：

		$n$
		$1$	$2$
$a$	$1$	$1$	$1$
	$2$	$2$	$1$

$p=5$ の場合：

		$n$
		$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

$p=7$ の場合：

		$n$
		$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$

$p=11$ の場合：

		$n$
		$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$8$	$5$	$10$	$9$	$7$	$3$	$6$	$1$
	$3$	$3$	$9$	$5$	$4$	$1$	$3$	$9$	$5$	$4$	$1$
	$4$	$4$	$5$	$9$	$3$	$1$	$4$	$5$	$9$	$3$	$1$
	$5$	$5$	$3$	$4$	$9$	$1$	$5$	$3$	$4$	$9$	$1$
	$6$	$6$	$3$	$7$	$9$	$10$	$5$	$8$	$4$	$2$	$1$
	$7$	$7$	$5$	$2$	$3$	$10$	$4$	$6$	$9$	$8$	$1$
	$8$	$8$	$9$	$6$	$4$	$10$	$3$	$2$	$5$	$7$	$1$
	$9$	$9$	$4$	$3$	$5$	$1$	$9$	$4$	$3$	$5$	$1$
	$10$	$10$	$1$	$10$	$1$	$10$	$1$	$10$	$1$	$10$	$1$

$p=13$ の場合：

		$n$
		$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$8$	$3$	$6$	$12$	$11$	$9$	$5$	$10$	$7$	$1$
	$3$	$3$	$9$	$1$	$3$	$9$	$1$	$3$	$9$	$1$	$3$	$9$	$1$
	$4$	$4$	$3$	$12$	$9$	$10$	$1$	$4$	$3$	$12$	$9$	$10$	$1$
	$5$	$5$	$12$	$8$	$1$	$5$	$12$	$8$	$1$	$5$	$12$	$8$	$1$
	$6$	$6$	$10$	$8$	$9$	$2$	$12$	$7$	$3$	$5$	$4$	$11$	$1$
	$7$	$7$	$10$	$5$	$9$	$11$	$12$	$6$	$3$	$8$	$4$	$2$	$1$
	$8$	$8$	$12$	$5$	$1$	$8$	$12$	$5$	$1$	$8$	$12$	$5$	$1$
	$9$	$9$	$3$	$1$	$9$	$3$	$1$	$9$	$3$	$1$	$9$	$3$	$1$
	$10$	$10$	$9$	$12$	$3$	$4$	$1$	$10$	$9$	$12$	$3$	$4$	$1$
	$11$	$11$	$4$	$5$	$3$	$7$	$12$	$2$	$9$	$8$	$10$	$6$	$1$
	$12$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$

オイラーの定理

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

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

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

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

カーマイケルの定理

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

たとえば、$n=10000$ のとき、カーマイケルの定理によれば $n$ と互いに素なすべての $a$に対して $a^m\equiv 1(\mathrm{mod}n)$ を満たす最小の $m$ は500であるが、特定の $a=7$ に対しては $7^{100}\equiv 1(\mathrm{mod}n)$　が成立する。

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

$n=2^e$ なら、

$\lambda (2^e)=\{\begin{array}{cc}1& (e=1)\\ 2& (e=2)\\ 2^{e-2}& (e\ge 3)\end{array}$

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

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

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

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

ここで $\mathrm{lcm}$ は最小公倍数。

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

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

が成り立つという定理である。

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

フェルマーテスト

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

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

対偶

$n$ と互いに素な整数 $a$ が

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

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

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

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

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

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

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

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

一般化

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

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
  • テンプレート:Cite book

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:MathWorld
• テンプレート:MathWorld
• テンプレート:MathWorld