次: 原始根と指数 上: フェルマの小定理 前: 循環小数

算術級数の定理

自然数を大きさの順に $1,\ 2,\ 3,\ \cdots$と並べたなかに素数がどのような法則にしたがって分布しているのか これは極めて難しい問題である.『素数』の冒頭にも述べたように多くの問題が未解決である．そのなかで素数の分布に関する著しい大定理を紹介し，フェルマの小定理の応用として，特別な場合を証明しよう．

歴史的に無限等差数列のことを算術級数，無限等比数列のことを幾何級数という．

算術級数中の素数の分布

算術級数 $a+dk\ (k=0,\ 1,\ 2,\ \cdots)$のなかにどのように素数が分布しているのか．いくつかの実験をしてみよう． 初項$a$と公差$d$が互いに素でなければすべてが最大公約数の倍数になるので，素数の分布を考えるときは互いに素とする．

$$\begin{eqnarray*} a=1,\ d=4&&1,\ 5,\ 9,\ 13,\ 17,\ 21,\ 25,\ 29,\ 33,\ 37,\ 41,... ...d=3&&2,\ 5,\ 8,\ 11,\ 14,\ 17,\ 20,\ 23,\ 26,\ 29,\ 32,\ \cdots \end{eqnarray*}$$

となり，初項と公差が互いに素な算術級数中には素数が無数に存在するように見える． 実は次の命題が成り立つ．

定理 26 (算術級数の定理(ディリクレの定理))
初項 $a(>0)$ と公差 $d\ (\ >0)$ がともに自然数でかつ互いに素であるような 算術級数の項の中には素数が無数に存在する． ■

算術級数の定理を完全に証明したのはディリクレ(Dirichlet)である(1837)．この定理の証明は簡単ではない．級数の理論を整数問題に応用する『解析的整数論』の発端となった．それは『数論初歩』の範囲を越える． ただ初項が$a=1$の場合，解析的方法を用いないで証明することができる．

定理 27
$m$ を任意の自然数とする． $1+mt\ (t \in \mathbb{Z})$ 型の素数が無限に存在する． ■

証明

【1】    $4n-1$ 型の素数が無数にあることを示す．

$4n-1$ 型の素数が有限個しかないとし，その最大のものを $p$ とする． つまり， $3,\ 7,\ \cdots,\ p$が$4n-1$ 型の素数の全体であるとする． これら$4n-1$ 型の素数全体の積に4をかけ1を減じた数を $a$ とする．つまり

$$a=4(3 \cdot 7 \cdot 11 \cdots \cdot p)-1$$

$a$は $a\equiv -1\quad (\bmod.\ 4)$ なので奇数である． したがってその約数はすべて奇数であるから，4を法として1または$-1$と合同である． $4k+1$ 型の数をいくらかけても$4k+1$型の数になるので， $4n-1$ 型の数の約数の中には必ず$4n-1$ 型の数がある． したがって$a$の素因数の中に$4n-1$ 型のものがある．

ところがこれは3から $p$ の$4n-1$ 型の素数のいずれとも互いに素であるから， $3,\ 7,\ \cdots,\ p$以外の素数である． つまり $3,\ 7,\ \cdots,\ p$が$4n-1$ 型の素数のすべてであるという仮定と矛盾した． つまり$4n-1$ 型の素数が無数にあることが示された．

【2】     $4n+1$ 型の素数が無数にあることを示す．

$4n+1$ 型の素数が無数にあることは簡単ではない． その証明にはフェルマの小定理が必要である． フェルマの小定理を応用して$4n+1$ 型の素数が無数にあることを証明しよう．

その基本となる事実は，$x^2+1$ の形をした数の素因数は 2 かまたは$4n+1$型の素数にかぎる，ということである． いくつか調べてみると

$$1^2+1=2,\ 2^2+1=5,\ 3^2+1=2\cdot 5,\ 4^2+1=17,\ 5^2+1=2\cdot 13,\ 6^2+1=37,\ \cdots$$

で確かにそうなっている．

つねに成立することは，次のように示される．

$x^2+1$が 2 以外の素数 $p$ で割り切れるとする．

$$x^2+1\equiv 0\quad (\bmod.\ p)$$

つまり

$$x^2\equiv -1\quad (\bmod.\ p)$$

ゆえに

$$x^4\equiv 1\quad (\bmod.\ p)$$

$x$ の指数は4である．そうでなければ4の約数の1か2の指数で

$$x\equiv 1\quad (\bmod.\ p)\quad ,\ または\quad x^2\equiv 1\quad (\bmod.\ p)$$

いずれからも $x^2+1\equiv 0\quad (\bmod.\ p)$ とあわせて

$$-1\equiv 1\quad (\bmod.\ p)$$

となる． $p\ne 2$ なのでこれはあり得ない． したがって定理24により， $p-1$ は4の倍数である．これを$p-1=4n$ とすれば

$$p=4n+1$$

この事実の応用として$4n+1$ 型の素数が無数にあることが示される．

$4n+1$ 型の素数が有限個しかないとする．その最大のものを $p$ とし，2とそれら$4n+1$ 型の素数すべての積の平方に1を加えた数を $a$ とする．つまり

$$a=(2\cdot 5 \cdot 13 \cdots \cdot p)^2+1$$

$a$の素因数 $q$ は奇数であるから2ではない． $x^2+1$型の数の素因数はすべて$4n+1$ 型の素数であるから，$q$は$4n+1$ 型の素数である． しかし $a$ は$p$ までの$4n+1$ 型の素数では割り切れないから， $q$ は $5,\ 13,\ \cdots,\ p$ 以外の$4n+1$ 型の素数である．

これは $5,\ 13,\ \cdots,\ p$ が$4n+1$ 型の素数のすべてであるという仮定と矛盾する． ゆえに$4n+1$ 型の素数が無数にあることが示された．

【3】     $mt+1$ 型の素数は無数に存在することを示す．

つまり，$m$ を2以上の任意の整数とするとき， 初項が1で公差が $m$ の等差数列の中に無数の素数が存在していることを証明する．

この証明は， $m=4$ の場合つまり $4n+1$ 型の素数が無数に存在することの証明を一般化することで得られる． $4n+1$ 型の素数が無数に存在することの証明に現れた $x^2+1$ は何か． それは定理22の$F_4(x)$ に他ならない． 1の原始4乗根 $\pm i$ のみを根とする多項式である．

そこで与えられた $m$ に対して $F_m(x)$ を考えよう． $a$ を $F_m(a)\ne \pm 1$であるような任意の整数とする． このとき $F_m(a)$ の素因数は$m$ の約数， または $mt+1$ の型のものにかぎられることを示す．

定理22によって次の等式が成り立つ．

$$x^m-1=F_m(x)G(x)$$

ここで $G(x)$ は $x$ の整数係数の整式である．

$$a^m-1=F_m(a)G(a)$$

において， $F_m(a),\ G(a)$ は整数であるから，素数 $p$ を $F_m(a)$ の素因数 とすれば， $a^m-1$ も $p$ の倍数である．つまり

$$a^m\equiv 1\quad (\bmod.\ p)$$

$a$ の指数を $e$ とする．定理24から $e$ は $m$ の約数で

$$m=ef$$

とおける． ここで$m>e$ とすれば $x^m-1$ は$x^e-1$ を因数にもつが，一方 $x^e-1$ と $F_m(x)$ は共通因数をもたないので($F_m(x)$ の根は $m$ 乗してはじめて1となる ものであるから)

$$x^m-1=(x^e-1)F_m(x)H(x)$$ (2.31)

ここで $G(x)=(x^e-1)H(x)$ が整数係数なので $H(x)$も整数係数の整式である． 等式(2.31)の両辺を $x^e-1$ で割る．

$$x^{e(f-1)}+x^{e(f-2)}+\cdots+x^e+1=F_m(x)H(x)$$

$x=a$ を代入して $a^e\equiv 1\quad (\bmod.\ p)$ を用いれば

$$f\equiv F_m(a)H(a)\equiv 0\quad (\bmod.\ p)$$

ゆえに $p$ は $f$ の約数，したがって $m=ef$ の約数である．

次に $m=e$ なら $m$ が $a$ の指数であるから $m$ は $p-1$ の約数である．つまり $p=mt+1$ と書ける． ゆえに， $F_m(a)\ne \pm 1$ のとき $F_m(a)$ の素因数は $m$ の約数，または $mt+1$ の型のものであることが示せた． 特に $a$ を$m$ に含まれるすべての素因数の積の倍数 とすれば， $a^m\equiv 1\quad (\bmod.\ p)$ より $(a,\ p)=1$ なので $p$ は $m$ の約数 ではあり得ない．したがってこのような $a$ をとるなら $p$ は必ず $mt+1$ の型の素数である．

$F_m(a)\ne \pm 1$ を仮定したが， $F_m(a)=\pm1$となる $a$ は有限個なのでそれ以外の $a$ はをとればよい． ゆえに任意の整数 $m$ に対して $mt+1$ 型の素数が存在することが示された．

もし $mt+1$ 型の素数が有限個しかなければ，最大のものを $p=mt+1$ とする． $m$ は任意なので $m$ の代わりに $mp$ をとると $p'=mpt+1$ 型の素数もまた存在する． ところが $p'$ は $mt+1$ 型の素数でもありしかも $p$ より大きい． したがって $p$ の最大性と矛盾するので， $mt+1$ 型の素数は無数に存在する． □

例 2.4.4   $m=12$ とする．

$$x^{12}-1=(x^6+1)(x^6-1)=(x^6+1)(x^2-1)(x^4+x^2+1)$$

で $F_{12}(x)=x^4+x^2+1$ ． $a=6$ とすると

$$F_{12}(6)=6^4-6^2+1=1261=13\times 97$$

で

$$13\equiv 1,\ 97\equiv 1\quad (\bmod.\ 12)$$

次: 原始根と指数 上: フェルマの小定理 前: 循環小数