初等整数論/フェルマーの小定理

整数論における重要な定理のいくつかは、合同式を用いるとそのステートメントを簡潔に書き表すことができる。その中の一つ、フェルマーの小定理について解説し、そこからわかる、素数を法とする剰余類の構造について解説する。また、合わせて合同式によって素数を特徴づけるウィルソンの定理についても触れる。

フェルマーの小定理

定理 2.2.1 (w:フェルマーの小定理)

p を素数、a を p で割り切れない自然数とすると、$a^{p-1}\equiv 1(\mathrm{mod}p)$

証明 1 上記の合同式の性質より、「$a^p\equiv a(\mathrm{mod}p)$」を示せばよい。この命題を a に関する数学的帰納法で証明する。a =1のとき成立することは自明である。a での成立を仮定して a +1 での成立を示す。二項定理より

$(a+1{)}^p=a^p+(\genfrac{}{}{0ex}{}{p}{1})a^{p-1}+\dots +(\genfrac{}{}{0ex}{}{p}{p-1})a+1\equiv a^p+1(\mathrm{mod}p)$ （$\because (\genfrac{}{}{0ex}{}{p}{1}),\dots ,(\genfrac{}{}{0ex}{}{p}{p-1})$ は $p$ の倍数であるため）

であり、帰納法の仮定より

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

なので、

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

証明 2
$\gcd (a,p)=1$ より、定理 1.8 から $0=0a,a,2a,3a,\cdots ,(p-1)a$ は p で割ったとき全ての余り $0,1,2,3,\cdots ,p-1$ を網羅している。余りが 0 すなわち割り切れるのは $0$ であるから、$a,2a,3a,\cdots ,(p-1)a$ は全ての余り $1,2,3,\cdots ,p-1$ を網羅する。

したがって、定理 2.1 の (v) より $1\cdot 2\cdot 3\cdots (p-1)\equiv a\cdot 2a\cdots 3a\cdots (p-1)a⟺(p-1)!\equiv a^{p-1}(p-1)!(\mathrm{mod}p)$

ここで、$p$ は素数なので、$(p-1)!$ とは互いに素。したがって、定理 2.1.1 (vi) より、両辺を $(p-1)!$ で割って定理を得る。

この定理は単純な定理であるが、とても強力である。この定理を用いれば、合同式について、はじめにあげた問題は次のように解くことができる。

7は素数であり12345は7で割り切れないので、$12345^6=12345^{7-1}\equiv 1(\mathrm{mod}7)$である。つまり求める余りは1である。

フェルマーの小定理の逆は必ずしも正しくない。つまり $n$ が合成数であるにもかかわらず $a\equiv ̸1(\mathrm{mod}p),a^{n-1}\equiv 1(\mathrm{mod}p)$ となる整数 $a$ が存在する場合がある。たとえば $2^{340}\equiv 1(\mathrm{mod}341)$ である。実際 $2^{10}-1=1023=3\dot{1}1\dot{3}1$ より $2^{10}\equiv 1(\mathrm{mod}341)$ である。このような数は擬素数と呼ばれる。さらに厄介なことに、 $\gcd (a,N)=1$ となる任意の $a$ に対し $a^{N-1}\equiv 1(\mathrm{mod}N)$ となる合成数 $N$ が存在する。そのような場合 $a^{N-1}\equiv ̸1(\mathrm{mod}N)$ となる $a$ を見つけるのは $N$ の素因数を見つけるのと同等の困難さを伴うことになる。このような数をカーマイケル数という。たとえば $561=3\cdot 11\cdot 17$ はカーマイケル数である（この場合は3で割り切れることがすぐに分かるが）。

したがって、フェルマーの小定理のみで与えられた数が素数かどうか判定することはできない。しかし、素数判定法の実行に先立ってフェルマーの小定理が成り立つかどうか確認することで多くの場合に、素数判定に時間を費やすことなく合成数であることを確認することができる。

なお、「小定理」というのは、同じフェルマーによる「大定理」（「フェルマーの最終定理」とも呼ばれる）があるからである。大定理は小定理とは同じフェルマーが予想した（フェルマーは証明を残さない数学者だった）整数論の定理であること以外は無関係であり、合同式も登場しないが、余談としてここに掲載しておく。

定理(Fermat-Wiles)

$x^n+y^n=z^n$

を満たすような整数$x,y,z,n(x,y,z\ge 1,n\ge 3)$は存在しない。

17世紀にフェルマーが予想したこの2つの定理だが、小定理は数十年後に証明されたのに対し、最終定理が証明されたのは1995年のことである。もちろんこの証明は初等的ではなく、この教科書の程度を超えるので、ここでは紹介しない。

位数

素数 $p$ に対して、フェルマーの小定理より、$\gcd (a,p)=1\Rightarrow a^{p-1}\equiv 1(\mathrm{mod}p)$ だったので、

$2^6\equiv 1(\mathrm{mod}7)$ となる。ここで、$2^n$ という形で、7 を法として 1 と合同になる最小の $n$ を探してみよう。$2^1\equiv 2,2^2\equiv 4,2^3\equiv 1(\mathrm{mod}7)$ となり、3 が最小だと分かった。

一般に、正の整数 $N$ とこれに互いに素な数 $a$ について、$a^n\equiv 1(\mathrm{mod}N)$ となる最小の自然数 $n$ を、「$N$ を法とした $a$ の位数」という。 $N$ を法とした $a$ の位数を ${\mathrm{o}\mathrm{r}\mathrm{d}}_N(a)$ と書くことがあるが、この表記はp進位数という別の意味を持つこともあるので注意する必要がある。

当面は素数を法とする位数について論じることとする。位数に関して、次の命題はほぼ自明だが、基本的な事実である。

命題 $a$ を素数 $p$ と互いに素な数とし、$a(\mathrm{mod}p)$ の位数を $e$ とする。このとき $1,a,a^2,\dots ,a^{e-1}$ は合同方程式

$X^e-1\equiv 0(\mathrm{mod}p)$

のすべての解である。

実際、$a^i(i=0,1,\dots ,e-1)$ がこの合同方程式の解であることは $(a^i{)}^e\equiv (a^e{)}^i\equiv 1(\mathrm{mod}p)$ から、すぐにわかる。また $0\le h<k\le e-1$ ならば $0<k-h<e$ より $a^k\equiv a^h{a}^{k-h}\equiv ̸a^h(\mathrm{mod}p)$ となるから $a^i(i=0,1,\dots ,e-1)$ はどの2つも $p$ を法として互いに非合同である。よって合同多項式の基本定理から $a^i(i=0,1,\dots ,e-1)$ がこの合同方程式のすべての解である。

フェルマーの小定理より、少なくとも $n=p-1$ は $a^n\equiv 1(\mathrm{mod}p)$ を満たすので、少なくとも素数を法とする場合には位数は確かに存在し、高々 $p-1$ であることがわかる。実のところ一般の正の整数を法とする場合についても、位数が存在することがわかるのだが、それは後に示すことにする。 さらに強く、素数を法とするとき、以下の通り位数は $p-1$ の約数である。

定理 2.2.2 (位数の法則)

正の整数 $N$ を法として、これに互いに素な数 $a$ の位数を $e$ とおく。このとき、$a^n\equiv 1(\mathrm{mod}p)⟺e|N.$

特に素数 $p$ を法とするときは $e|p-1$ である。

証明
前段の $\Leftarrow$ は自明なので $\Rightarrow$ を証明する。

除算の原理に基づいて $n=eq+r(0\leqq r<e)$ とする。これを $a^n\equiv 1(\mathrm{mod}N)$ に代入して、

$a^r\equiv (a^e{)}^q{a}^r\equiv a^{eq+r}\equiv 1(\mathrm{mod}N)$

を得る。ここで、$0<r<e$ とすると、$e$ の最小性に反するので、$r=0.$ したがって、$n=eq$ であるから、前段の $\Rightarrow$ が示された。

フェルマーの小定理より $p$ が素数ならば $a^{p-1}\equiv 1(\mathrm{mod}p)$ であるから 前段より$e|p-1$ である。これにより定理の主張はすべて証明された。

位数の法則から、次の事実がわかる。

定理 2.2.2'

$a(\mathrm{mod}N)$ の位数が $e$ であるための必要十分条件は

• $a^e\equiv 1(\mathrm{mod}N),$
• $e$ のすべての素因数 $q$ に対して $a^{e/q}\equiv ̸1(\mathrm{mod}N)$

が共に成り立つことである。

証明
必要性は定義からすぐに導かれる。

十分性を証明する。 1つめの条件と位数の法則から、$a(\mathrm{mod}N)$ の位数は $e$ の約数である。 $a(\mathrm{mod}N)$ の位数が $e/l,l>1$ であったとすると $l$ の素因数 $q$ をとれば

$a^{e/q}\equiv (a^{e/l}{)}^{l/q}\equiv 1(\mathrm{mod}N)$

となり、2つめの条件に反する。

位数の法則の系として、特殊な形の数の素因数、および等差数列上の素数について次のようなことがわかる。

系1 $n^2+1$ の形の数の素因数は 2 もしくは $4m+1$ の形をしている。さらに一般に $n^{2^k}+1$ の形の数の素因数は 2 もしくは $m\cdot 2^{k+1}+1$ の形をしている。

$p$ が $n^{2^k}+1$ の奇数の素因数ならば $n^{2^k}\equiv -1(\mathrm{mod}p)$ であるから2乗して

$n^{2^{k+1}}\equiv 1(\mathrm{mod}p)$

であることがわかる。したがって定理 2.2.2 の前段より $n(\mathrm{mod}p)$ の位数は $2^{k+1}$ の約数である。しかし $n^{2^k}\equiv -1(\mathrm{mod}p)$ かつ $p>2$ だから $n^{2^k}\equiv ̸1(\mathrm{mod}p)$ であるから $n(\mathrm{mod}p)$ の位数は $2^{k+1}$ でなければならない。よって定理 2.2.2 の後段より $p\equiv 1(\mathrm{mod}{2}^{k+1})$ である。

系2 $p$ を素数とする。 $n^{p-1}+n^{p-2}+\cdots +1$ 形の数の素因数は $p$ もしくは $ap+1$ の形をしている。

$q$ が $n^{p-1}+n^{p-2}+\cdots +1$ の素因数ならば $n^p-1\equiv (n-1)(n^{p-1}+n^{p-2}+\cdots +1)\equiv 0(\mathrm{mod}q)$ すなわち

$n^p\equiv 1(\mathrm{mod}q)$

である。したがって定理 2.2.2 の前段より $n(\mathrm{mod}q)$ の位数は $p$ の約数、すなわち 1 または $p$である。 $n(\mathrm{mod}q)$ の位数が 1 ならば $n\equiv 1(\mathrm{mod}q)$ より

$0\equiv n^{p-1}+n^{p-2}+\cdots +1\equiv p(\mathrm{mod}q)$

となるから、$q=p$ でなければならない。 $n(\mathrm{mod}q)$ の位数が $p$ ならば定理 2.2.2 の後段より $q\equiv 1(\mathrm{mod}p)$ である。

ここから、

$(2\cdot 3\cdot 5\cdots p{)}^2+1$

あるいは

$P^{p-1}+P^{p-2}+\cdots +1(P=2\cdot 3\cdot 5\cdots q)$

といった形の数を考えることで 任意の自然数 $n$ に対し $m\cdot 2^n+1$ の形の素数が無限に多く存在し、任意の素数 $p$ に対し $ap+1$ の形の素数が無限に多く存在する ことがわかる。

また、系1から、特に素数が無限に多く存在することの証明3でふれたフェルマー数 $F_k=2^{2^k}+1$ の素因数は $m\times 2^{k+1}+1$ の形でなければならないことがわかる（実は平方剰余の理論から、さらに強く $m\cdot 2^{k+2}+1$ の形でなければならないこともわかる）。素数が無限に多く存在することの証明3でも述べたようにフェルマー数はどの2つも互いに素であるから、$F_{n-1},F_n,F_{n+1},F_{n+2},\dots$ の素因数を考えることにより、やはり任意の自然数 $n$ に対し $m\cdot 2^n+1$ の形の素数は無限に多く存在することが導かれる。

位数については、次の定理も成り立つ。

定理 2.2.3

法 $N$ に関して、$a$ の位数が $e$ のとき、$a^k$ の位数は、$E=\frac{e}{\gcd (k,e)}$ である。

証明
$\gcd (k,e)=d,k=k^{\prime }d,e=Ed$ とおけば、$(k^{\prime },E)=1$ である。

位数の法則より $(a^k{)}^x\equiv 1⟺a^{kx}\equiv 1(\mathrm{mod}N)⟺e|kx⟺E|k^{\prime }x$ である。 $(k^{\prime },E)=1$ であるから、定理 1.6 より、これは $E|x$ と同値である。 よって $a^k$ の $p$ を法とする位数は $E$ である。

また、次の定理も位数に関する事実として重要である。

定理 2.2.4

$i=1,2,\dots ,k$ に対し $a_i(\mathrm{mod}N)$ の位数を $e_i$ とする。 $e_i$ がどの2つも互いに素ならば、$\prod _{i=1}^k{a}_i(\mathrm{mod}N)$ の位数は $\prod _{i=1}^k{e}_i$ に一致する。

証明
$E=\prod _{i=1}^k{e}_i=e_j{m}_j(j=1,2,\dots ,k)$ とおく。つまり $m_j=\prod _{1\le i\le k,i\ne j}{e}_i$ である。

$(\prod _{i=1}^k{a}_i{)}^E\equiv \prod _{i=1}^k{a}_i^E\equiv \prod _{i=1}^k{a}_i^{e_i{m}_i}\equiv \prod _{i=1}^k(a_i^{e_i}{)}^{m_i}\equiv 1(\mathrm{mod}N)$

より $\prod _{i=1}^k{a}_i(\mathrm{mod}N)$ の位数は $E=\prod _{i=1}^k{e}_i$ の約数である。

ここで定理 2.2.2' を用いて位数が正確に $E$ に一致することを示す。まず $j=1,2,\dots ,k$ を1つとって、さらに $e_j$ の素因数を1つとり、それを $q$ とする。

$(\prod _{i=1}^k{a}_i{)}^{E/q}\equiv \prod _{i=1}^k{a}_i^{E/q}(\mathrm{mod}N)$

であるが。ここで $i\ne j$ とすると、仮定より $\gcd (e_i,e_j)=1$ だから $e_i$ は $q$ で割り切れない。よって $e_i$ は $E/q$ の約数であるから $a_i^{E/q}\equiv 1(\mathrm{mod}N)$ である。したがって

$(\prod _{i=1}^k{a}_i{)}^{E/q}\equiv \prod _{i=1}^k{a}_i^{E/q}\equiv a_j^{E/q}(\mathrm{mod}N).$

一方、やはり仮定より $e_i$ はどの2つも互いに素だから $\gcd (e_j,m_j)=1$ である。よって $e_j$ は $E/q=m_j(e_j/q)$ を割り切らない。よって

$(\prod _{i=1}^k{a}_i{)}^{E/q}\equiv a_j^{E/q}\equiv ̸1(\mathrm{mod}N).$

$q$ は$E$ の素因数から任意に取れるから定理 2.2.2' より $\prod _{i=1}^k{a}_i(\mathrm{mod}N)$ の位数は $E$ に一致する。

ウィルソンの定理

自然数 $p>1$ について、$p$ が素数 $⟺(p-1)!\equiv -1(\mathrm{mod}p).$

証明 1
$p$ は素数なので、$1\leqq m<p$ なる $m$ は $p$ と互いに素。したがって、定理 1.8 より、

$m,2m,3m,\cdots (p-1)m$ は全て $p$ で割った余りが異なるので、$mn\equiv 1(\mathrm{mod}p)$ なる $n$ が存在する。

このとき、$n=m$ とすると、$m^2\equiv 1⟺(m-1)(m+1)\equiv 0(\mathrm{mod}p)\cdots (1)$

すなわち、$(m-1)(m+1)$ は素数 $p$ で割り切れるので、定理 1.12 より $m-1$ が $p$ で割り切れる、または $m+1$ が $p$ で割り切れるはずである。よって、

$(1)⟺m-1\equiv 0\vee m+1\equiv 0(\mathrm{mod}p)$

$1\leqq m<p$ なので、

$m=1\vee m=p-1$

以上をまとめると、$m=n\Rightarrow m=1\vee p-1$ となる。対偶を取って、

$⟺m\ne \wedge m\ne p-1\Rightarrow m\ne n$

よって、$mn=1$ となるような組を$\frac{p-3}{2}$ 個作ることによって、

$\begin{array}{cc}(p-1)!& \equiv 1^{\frac{p-3}{2}}\cdot 1\cdot (p-1)\\ & \equiv 1\cdot 1\cdot (-1)\\ & \equiv -1(\mathrm{mod}p)\end{array}$

次に、$p$ が素数でない $⟺(p-1)!\equiv ̸-1(\mathrm{mod}p)$ を証明する。

まず、$p=4$ のとき、$(4-1)!=6\equiv 2\equiv ̸-1(\mathrm{mod}p)$ であるから、定理は成り立つ。

$p>4$ のとき、$p$ は合成数なのだから、$p=ab$ と表せる。もちろん、$a,b\leqq p-1$

$a\ne b$ならば、$(p-1)!=(p-1)(p-2)\cdots 2\cdot 1$ は、$a,b$ を因数に持つので $(p-1)!$ を割り切る。したがって、$(p-1)!\equiv 0(\mathrm{mod}p)$ となる。

$a=b$ ならば、$p>4$ より、$2<a$ となる。$(p-1)!$ は $a$ を因数として含む。また、

$\begin{array}{cc}2<a& \Rightarrow 2a<a^2\\ & ⟺2a<ab\\ & ⟺2a<ab\\ & ⟺2a<p\\ & ⟺2a\leqq p-1\\ \end{array}$

したがって、$(p-1)!=(p-1)\cdots 2a\cdots a\cdots 2\cdot 1$

となり、$a^2=ab=p$ で割り切れる。

ゆえにどちらの場合も、$p$ が素数でない $⟺(p-1)!\equiv 0\equiv ̸-1(\mathrm{mod}p)$

以上より同値であることが分かり、ウィルソンの定理が証明された。

証明 2 次に、$p$ が素数でない $⟺(p-1)!\equiv ̸-1(\mathrm{mod}p)$ の証明は上記の通り。

$p$ が素数のときフェルマーの小定理より合同式 $X^{p-1}-1\equiv 0(\mathrm{mod}p)$ は解 $1,2,\dots ,p-1$ を持つ。よって合同多項式の基本定理より

$X^{p-1}-1\equiv g(X)(X-1)(X-2)\cdots (X-(p-1))(\mathrm{mod}p)$

となるが、$X^{p-1}-1,(X-1)(X-2)\cdots (X-(p-1))$ は共に最高次の係数が1の$p-1$次多項式なので、$g(X)\equiv 1(\mathrm{mod}p)$ つまり

$X^{p-1}-1\equiv (X-1)(X-2)\cdots (X-(p-1))(\mathrm{mod}p)$

である。$X=0$ を代入し

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

となることがわかる（一番右の合同式は $p$ が奇数のときは $(-1{)}^{p-1}=1$ から、$p=2$ のときは $-1\equiv 1(\mathrm{mod}2)$ から）。

フェルマーの小定理と異なり、ウィルソンの定理は素数であることの必要十分条件をあらわしている。しかし、この定理を大きな数の素数判定に用いることは実用的ではない。というのは階乗を高速に計算する方法が知られていないからである。