次: 演習問題 上: 素数 前: 素数の定義

素因数分解

さて，合成数は素数の積として順序を除けばただ一通りに表すことができる． これが素因数分解の一意性といわれる基本定理である．

定理 7
     2以上の整数を素数の積に分解することができる． かつ，その分解の結果は（因数の順序をのぞけば）一意である．■

証明     2以上の整数$n$に関する数学的帰納法で示す．

(1)     $n=2$のとき$2=2$と素数1個の積なので成立．

(2)     $a$ よりも小さい2以上の整数については定理が成立していると仮定する．

$a$の分解の可能性を示す． $a$が素数なら$a$自身が素数1個の積である． $a$が合成数のとき．

$$a=b\times c\quad (1<b<a,\ 1<c<a)$$

と分解される．数学的帰納法の仮定により $b$ も $c$ も素数の積に分解されるので，$a$ も素数の積に分解される．

$a$の分解の一意性を示す． $a$ を素因数に分解して二つの分解

 

 

$$a=p_1p_2\cdots p_m=q_1q_2\cdots q_n$$

を得たとする．定理2の(4)より，二つの整数の積が素数 $p$ で割り切れるなら， 因数のなかの少なくとも一つがその素数で割り切れる．三つ以上の数以上の積の場合も $abc=(ab)c$ のように括弧でくくり順次考えれば，いずれかが $p$ の倍数になる．したがって， $p_1,\ p_2,\ \cdots,\ p_m$ のいずれかは $q_1$ で割り切れる．いま $p_1$ が $q_1$ で割りきれるとすれば, $p_1$ は素数なので, $p_1=q_1$ である．

$$∴\quad p_2\cdots p_m=q_2\cdots q_n$$

この両辺の数を $b$ とすれば $b<a$ なので数学的帰納法の仮定からこの分解は順序を除いて一意である． よって$a$において定理が成立する．

(3)     (1)(2)より，2以上の任意の整数に対して定理が成立することが示された．□

因数分解の一意性の別証明

次のような除法を用いない因数分解の一意性の証明がある.『数学のたのしみ』(2006年夏号，日本評論社)の「素数・ゼータ関数・三角関数」(黒川重信)より紹介する．ツェルメロによるものである．

これは除法を用いていない．自然数の集合には最小のものが存在することだけを用いている．因数分解の可能性は同様なので，一意性のみ別証明をおこなう．

証明     異なる素因数分解をもつ自然数の集合を考える． この集合に属する最小の自然数を$n$とする． $n$は相異なる2つの因数分解をもつ．それを

$$\begin{eqnarray*} n=p_1p_2\cdots p_r&&(p_1\le p_2\le \cdots \le p_r)\\ n=q_1q_2\cdots q_s&&(q_1\le q_2\le \cdots \le q_s) \end{eqnarray*}$$

とする．ここに $p_1,\ \cdots,\ p_r,\ q_1,\ \cdots,\ q_s$ は素数である．これが異なる因数分解ということは $r\ne s$か，または$r=s$でとなる i が存在するか， のいずれかである．

また， $p_1,\ \cdots,\ p_r$のいずれも $q_1,\ \cdots,\ q_s$のいずれとも異なる． なぜなら，もし$p_i=q_j$なら， これを約せば$n$より小さい数で，異なる因数分解をもつ自然数が得られ， $n$がそのような数のなかで最小であることに反する．

$p_1<q_1$とする． ここで自然数$m$を

$$\begin{eqnarray*} m&=&n-p_1q_2\cdots q_s\\ &=&(q_1-p_1)q_2 \cdots q_s \end{eqnarray*}$$

で定める．$m<n$である．

この$m$の因数分解における因数$q_1-p_1$は$p_1$の倍数ではない． なぜならもし$p_1$の倍数なら$q_1$が$p_1$の倍数となり互いに異なる素数であることに反する． よってこの因数分解に$p_1$は現れない．

一方$m$は

$$\begin{eqnarray*} m&=&n-p_1q_2 \cdots q_s\\ &=&p_1(p_2 \cdots p_r-q_2 \cdots q_s) \end{eqnarray*}$$

でもある． この$m$の因数分解には，因数$p_1$が現れている．

よって$m$の2つの因数分解は相異なる因数分解である．

$m<n$なので， $n$が異なる2つの因数分解をもつ最小の自然数であることと矛盾した．

したがって異なる2つの因数分解をもつ自然数は存在しない．□

除法の原理自身，除法が一意に出来ることを示すためには自然数の集合に最小のものが存在することを用いた．だから，除法を使うか使わないかにかかわらず，自然数の性質が土台になっている．だから，このツェルメロの証明は，自然数の集合には最小のものが存在することをいったん除法の原理にまとめることをせず，自然数の性質から直接示す，ともいえる．

 

素数は無限に存在するのだろうか．この問題の解明は本質的にはユークリッドによってなされた．ユークリッドは『原論』のなかで，素数の個数が3個であるとして矛盾が起こるという形で議論した．つまり背理法である．ユークリッドは歴史に残る人のなかで，はじめて背理法を用いた人である．

定理 8
素数の個数は無限である．■

証明     背理法で示す．素数の個数が有限であると仮定する．その個数を $n$ 個とし， $p_1,\ p_2,\ \cdots,\ p_n$ をすべての素数とする． このとき

$$a=p_1p_2\cdots p_n+1$$

とおく．

定理39 より$a$は素数の積に分解される． 一方$a$は $p_1,\ p_2,\ \cdots,\ p_n$ のいずれで割っても1余る． つまり， $p_1,\ p_2,\ \cdots,\ p_n$ は$a$の約数でない． よって$a$ の素因数分解に現れる素数は $p_1,\ p_2,\ \cdots,\ p_n$ ではあり得ず， それら以外の素数である． これは $p_1,\ p_2,\ \cdots,\ p_n$ がすべての素数という仮定と矛盾する． ゆえに素数の数は無限である．□