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

素因数分解

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

定理 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$は相異なる二つの因数分解をもつ．それを

$$\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$で$p_i\ne q_i$となる$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$の二つの因数分解は相異なる因数分解である．

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

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

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

例 1.5.1        素因数分解の一意性を用いた論証の例をあげよう．(1)は次のことに注意したい． $p$が素数であるということは，$p$の約数が1と$p$以外にないということであり，これは整数$p$自身の内在的性質である．その性質をもつ$p$が，二つの整数の積$ab$の約数になれば，$a$か$b$少なくとも一方の約数になっている．これは$p$と他の整数との関係であり，外に向かう性質である．

(1)

$a$と$b$を整数，$p$を素数とする．$ab$が$p$で割り切れれば，$a$または$b$が$p$で割り切れる．

(2)

$\sqrt{2}$は有理数ではない．

それぞれ次のように素因数分解の一意性や，それににもとづく定理から示すことができる．

(1)

$ a $ が $ p $ で割り切れないとする． つまり $ a $ と $ p $ は互いに素であるとする． $ ab $ が $ p $ の倍数であるから，定理2の(4)によって， $ b $ は $ p $ の倍数である．
$ b $ が $ p $ で割り切れないときは $ a $が $ p $ の倍数になる． □

注意 1.5.1 『数論初歩』は定理2などを基礎に素数を定義し， 因数分解の一意性を示している．

一方，整数$p$素数であることを，

$$任意の整数aとbに対し 「pがabの約数なら，pはaまたはbの約数である」が成り立つ．$$

ような整数として定義することもできる．
この場合は逆にこの定義から因数分解の一意性が示せる． つまり素因数分解の一意性と，(1)は同値なのである．

どのように論を構成するかという問題よりも，どのような数学的現象とどのような数学的現象が同値であるかを確認することが重要である． このような問題は整域における整除問題として， 環の一般論のなかで諸定義相互の関係は明らかにされる．

(2)

有理数であるとし， $\sqrt{2}=\dfrac{n}{m}$とおく．これから

$$2m^2=n^2$$

右辺$n^2$の因数分解のなかに素因数2は偶数個ある． 左辺$2m^2$の因数分解のなかに素因数2は奇数個ある． これは素因数分解の一意性と矛盾する． よって$\sqrt{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$ がすべての素数という仮定と矛盾する． ゆえに素数の数は無限である．□

 

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