Fermatの小定理について

2019年6月4日作成

素数に関する重要な定理として、Fermatが発見した合同式に関する定理がある。

$a^n (n=0, 1, 2, 3, \ldots)$ を素数 $p$ で割った余りが $n$ に対してどのように変化していくかを考えよう。 もちろん $a$ が $p$ の倍数ならば $a^n$ も $p$ の倍数だから、余りはつねに $0$ である。したがって $a$ が $p$ の倍数でない場合が重要である。

$2^n$ を $7$ で割った余りは $1, 2, 4, 1, 2, 4, \ldots$ となり、その後 $1, 2, 4$ の繰り返しとなる。

$3^n$ を $7$ で割った余りは $1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, \ldots$ となり、その後 $1, 3, 2, 6, 4, 5$ の繰り返しとなる。

$2^n$ を $5$ で割った余りは $1, 2, 4, 3, 1, 2, 4, 3, \ldots$ となり、その後 $1, 2, 4, 3$ の繰り返しとなる。

もちろん、 $a=1$ ならば $a^n$ を $p$ で割った余りは常に $1$ である。

これらの例では、いずれもどこかで余りは $1$ となり、その後は同じパターンの繰り返しとなる。 $1$ になる場所はそれぞれ異なっている、同じ素数 $p=7$ でも $a=1, 2, 3$ でそれぞれ異なっているが、 少なくとも $p=7$ のとき $n=6$ ならば $a^n$ を $p$ で割った余りは $1$ となり、また $p=5$ のときは $n=4$ で $a^n$ を $p$ で割った余りは $1$ になると思われる。

Fermatはこれらのことから、（$a$ が $p$ の倍数でない限り） $a^n$ を $p$ で割った余りは $n=p-1$ で必ず $1$ になると考えた。つまり、次のことが成り立つと考えたのである。

Fermatの小定理

$p$ が素数で、 $a$ が $p$ で割り切れない整数ならば \[a^{p-1}\equiv 1\pmod{p}\] が成り立つ。

長年解決されなかったFermatの最終定理に対して、この定理をFermatの小定理という。 Fermatの最終定理同様、Fermatの小定理についてもFermat自身が証明を残したことは確認されておらず、 最初に証明を公表したのはEulerとされているが、Burton, History of mathematics/an introduction, 7th Ed., McGrawHill, 2011 の p.p.514-515 によればLeibnizがそれ以前に未公開の草稿の中で証明していた ようである。

LeibnizやEulerの証明は二項係数を用いたものである。すなわち $1\leq a\leq p-1$ ならば $\binom{p}{a}=p!/a!(p-a)!$ は（分子が $p$ の倍数だが分母が $p$ の倍数でないから） $p$ の倍数であるから $a^p\equiv a\pmod{p}$ ならば \[(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{1}a+1\equiv a^p+1\equiv a+1\pmod{p}\] が成り立つことから、数学的帰納法より $a^p\equiv a\pmod{p}$ がすべての自然数 $a$ について成り立つことがわかる。

一方で、Fermatの小定理は剰余の性質から自然に証明することもできる。 初等整数論の基本定理の証明の 第5節の最後に書いた注意点から $p$ 個の整数 $0, a, 2a, 3a, \ldots, (p-1)a$ を $p$ で割った余りは $0, 1, \ldots, p-1$ を1回ずつとる。ここから $0$ を除くと $p-1$ 個の整数 $a, 2a, 3a, \ldots, (p-1)a$ を $p$ で割った余りは $1, 2, \ldots, p-1$ を1回ずつとる。よって \[(p-1)! a^{p-1}=a\times (2a)\times \cdots (p-1)a\equiv (p-1)!\pmod{p}\] つまり \[(p-1)! (a^{p-1}-1)\equiv 0\pmod{p}\] となるが、となるが先述の文書内で証明したEuclidの補題から $(p-1)!$ は $p$ と互に素なので、 $a^{p-1}-1\equiv 0\pmod{p}$ が成り立つ。

---

Fermatの小定理は、素数で割った余りについて触れていたが、法が素数ではないときにはどうなるか？ $3^3\equiv 3\pmod{4}, 2^{14}\equiv 4\pmod{15}$ などから、 単純に一般化した式 $a^{n-1}\equiv 1\pmod{n}$ は成り立たない（しかし、 $n$ が素数でなく、かつ $a\equiv 1\pmod{n}$ ではないにも かかわらず、$a^{n-1}\equiv 1\pmod{n}$ が成り立つような場合はある）。 まず法が素数のべきである場合、次のような合同式が成り立つ。

Fermatの小定理の素数べきへの一般化

$p$ が素数、$e$ が正の整数で、 $a$ が $p$ で割り切れない整数ならば \[a^{p^{e-1}(p-1)}\equiv 1\pmod{p^e}\] が成り立つ。

実際 $a^{p-1}=Ap+1$ とおくと二項定理より \[a^{p^{e-1}(p-1)}=(Ap+1)^{p^{e-1}}=1+Ap^e+\frac{Ap^e(p^{e-1}-1)}{2}+\cdots \equiv 1\pmod{p^e}\] となる。

二項定理を使わず、Fermatの小定理の上記の証明を一般化した証明も可能である。 $u_k$ を $ka (0\leq k\leq p^e-1)$ を $p^e$ で割った余りとする。 $u_k$ は $0, 1, \ldots, p^e-1$ を1回ずつとる。 このうち $k$ が $p$ の倍数であるものを考える。それらは $p^{e-1}$ 個ある。 $k$ が $p$ の倍数ならば $ka$ を $p^e$ で割った余りも $p$ の倍数になるから それらは $p^{e-1}$ 個の値 $0, p, \ldots, (p^{e-1}-1)p$ を1回ずつとる。 よって $k$ が $p$ の倍数ではないものを考えると、それらは $p^e-p^{e-1}=p^{e-1}(p-1)$ 個あり、 $u_k$ は $0, 1, \ldots, p^e-1$ のうち $p$ で割れない値を1回ずつとる。よって \[\sideset{}{^*}\prod_k ka\equiv \sideset{}{^*}\prod_k k\pmod{p^e}\] となる。ここで積 $\sideset{}{^*}\prod_k$ における $k$ は $0, 1, \ldots, p^e-1$ のち $p$ で割れない数全体を走るとする。 積 $\sideset{}{^*}\prod_k k$ は $p$ で割れないから、先と同様に \[a^{p^{e-1}(p-1)}\equiv 1\pmod{p^e}\] が成り立つ。

なお、$p=2, e\geq 3$ のときはやや強く、 $a$ が奇数のとき \[a^{2^{e-2}}\equiv 1\pmod{2^e}\] が成り立つ。実際 $1^2\equiv 3^2\equiv 5^2\equiv 7^2\equiv 1\pmod{8}$ 、かつ \[a^{2^{e-2}}-1=A\times 2^e\] ならば \[a^{2^{e-1}}-1=A\times 2^e(a^{2^{e-2}}+1)=A\times \frac{a^{2^{e-2}}+1}{2}\times 2^{e+1}\] となる。

---

ここから、さらにFermatの小定理は一般の正の整数 $n$ にまで一般化される。 Carmichaelの関数 $\lambda(n)$ を奇素数べき $p^e$ および $p=2, e=1, 2$ に対しては \[\lambda(p^e)=p^{e-1}(p-1),\] $2$ の累乗 $2^e (e\geq 3)$ に対しては \[\lambda(2^e)=2^{e-2},\] 一般の整数 $n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ （$p_1, p_2. \ldots, p_k$ は相異なる素数） に対しては \[\lambda(p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k})=\mathrm{LCM}[\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), \ldots, \lambda(p_k^{e_k})]\] により定義する。 たとえば $\lambda(2)=1, \lambda(3)=\lambda(4)=\lambda(6)=\lambda(8)=2, \lambda(7)=\lambda(9)=6$ となる。 特に$\lambda(n)$ は $\prod_{i=1}^k p^{e-1}(p-1)$ の約数である。

Fermatの小定理の一般化

$n>0, a, n$ が互に素な整数ならば \[a^{\lambda(n)}\equiv 1\pmod{n}.\]

$n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ （$p_1, p_2. \ldots, p_k$ は相異なる素数） とおくと、先に述べたFermatの小定理の素数べきへの一般化から各 $i=1, \ldots, k$ に対して \[a^{\lambda(p_i^{e_i})}\equiv 1\pmod{p_i^{e_i}}\] が成り立つ。各 $\lambda(p_i^{e_i})$ は $\lambda(n)$ の約数だから \[a^{\lambda(n)}\equiv 1\pmod{p_i^{e_i}}\] が各 $i=1, 2, \ldots, k$ に対して成り立つ。すなわち $a^{\lambda(n)}-1$ は各 $p_i^{e_i}$ で割り切れる。 Euclidの補題の「双対」から、$a^{\lambda(n)}-1$ は $n$ で割り切れる。

特に $n=p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$ に対して \[\varphi(n)=\prod_{i=1}^k p^{e-1}(p-1)\] とおくと $\varphi(n)$ は $\lambda(n)$ の倍数だから \[a^{\varphi(n)}\equiv 1\pmod{n}\] が成り立つ。 $\varphi(n)$ は $1, 2, \ldots, n-1$ のうち $n$ と互に素なものの個数を与える関数で（証明は省略する）、 Eulerの $\varphi$ 関数とよばれる。

素数判定との関係

Fermatの小定理から $p$ が素数で $a$ が $p$ の倍数でない整数ならば $a^{p-1}\equiv 1\pmod{p}$ となる。 しかし、$n$ が素数でなく、かつ $a\equiv 1\pmod{n}$ ではないにも かかわらず、$a^{n-1}\equiv 1\pmod{n}$ が成り立つような場合はある。たとえば \[2^{340}\equiv 1\pmod{341}\] となる。

それで、Fermatの小定理を一つの数 $a$ に対して使うだけで $p$ が素数であることを 確かめることは出来ない。複数の $a$ を使うとどうなるか？実はこの場合も、 $a$ が $n$ と互いに素である限り $a^{n-1}\equiv 1\pmod{n}$ が常に成り立つような 合成数 $n$ が存在する。たとえば $561=3\times 11\times 17$ だが $a$ が $561$ と互いに素ならば \[a^{560}\equiv 1\pmod{561}\] は常に成り立つ。

もちろん $a$ が $n$ の（$1$ でも $n$ 自身でもない）約数であれば、 $a^n\equiv 1\pmod{n}$ は成り立たない。 しかし、そのような $a$ を見つけるのは結局 $n$ の $1$ でも $n$ 自身でもない約数を実際に見つけることを意味するから 素数の判定法としては、「$n$ の $1$ でも $n$ 自身でもない約数を実際に見つける」という 素朴な（かつ非常に時間のかかる）判定法に比べて簡単になっていないのである。

それにもかかわらず、Fermatの小定理は様々な素数判定法の基礎として重要であり、その他にも 数論において様々な形で用いられている。

乗法位数

\[a^e\equiv 1\pmod{n}\] となる最小の正の整数 $e$ を $a\pmod{n}$ の乗法位数（あるいは単に位数）という。 次の重要な事実が分かる。

\[a^m\equiv 1\pmod{n}\] ならば $m$ は $a\pmod{n}$ の乗法位数 $e$ の倍数である。 特に $a\pmod{n}$ の乗法位数は $\lambda(n)$ の約数である。

$m=qe+r, 0\leq r\leq e-1$ とおくと \[a^m\equiv a^{qe+r}\equiv a^r\pmod{n}\] より $a^r\equiv 1\pmod{n}$ だが、$0\leq r\leq e-1$ である。$r$ が正のとき $r$ は $e$ より小さい正の整数となってしまい、 $e$ を $a^e\equiv 1\pmod{n}$ となる最小の正の整数としたことに矛盾する。 よって $r=0$ である。つまり $m$ は $e$ の倍数である。

ここから、たとえば次のようなことがわかる。

$x^2+1$ の素因数は $2$ または $4n+1$ の形のものでなければならない。

$p$ を $x^2+1$ の奇数の素因数とする。 そうすると $x^2\equiv -1\pmod{p}$ より $x^4\equiv 1\pmod{p}$ だから $x\pmod{p}$ の乗法位数は $4$ の約数である。しかし $p\neq 2$だから $x^2\equiv -1\not\equiv 1\pmod{p}$ となる。よって $x\pmod{p}$ の乗法位数は $2$ の約数ではないので、正確に $4$ であることがわかる。 Fermatの小定理より $p-1$ は $4$ の倍数なので $p$ は $4n+1$ の形の素数でなければならない。

さらに、ここから、$4n+1$ の形の素数は無限に多く存在することがわかる。

実際、$4n+1$ の形の素数 $p_1, p_2, \ldots, p_r$ を任意にとれば、 $(2p_1 p_2 \cdots p_r)^2+1$ は奇数で $p_1, p_2, \ldots, p_r$ のいずれとも互いに素なので、 先の定理から、この数の素因数は $4n+1$ の形のものであり、かつそれは $p_1, p_2, \ldots, p_r$ とは異なるものでなければならない。