高校数学[総目次]
高校数学ワンポイント
9．素因数分解の一意性
$1,2,3,\cdots$ を自然数といいます．このうち1と自分自身しか約数をもたない数を素数といいますが，1だけは素数に含みません．具体的には $2,3,5,7,\cdots$ という数で，素数は無限にあることが知られています．素数と1以外の自然数を合成数といいます．合成数を素因数の積に分解することを素因数分解といいます．例えば，
\[6=2\times3,\ 15=3\times5,\ 18=2\times3^2\]
等々．中学生，あるいは小学生の時から慣れ親しんでいるものでしょうが，次の問いはどうでしょう？
Q1. どんな合成数も素因数の積に分解できるのか？
Q2. できるとすれば，分解の仕方は1通りか？
Q1 は合成数の「分解の可能性」について，Q2 は「分解の一意性」についてですが，答えはどちらもYESです．では証明は？と聞かれたらどうでしょう．教科書でも見たことがありません．
以下，これらについて証明していきます．尚，本稿では数といえば自然数(1以上の整数)であるとします．
9.1 分解の可能性
定理 合成数は素数の積に分解できる．
証明
数学的帰納法で示します．
1° 1番小さい合成数4は $2\times2$ と素数の積に分解できます．
2° ある合成数を $n$ とし，$n$ より小さい合成数はすべて素数の積に分解できるとします．$n$ は合成数ですから，$n$ より小さな数 $a,b$ を用いて $n=ab$ と書き表すことができます．
$a$ と $b$ が共に素数であれば，$n$ はもはや素数の積に分解できています．
次に $a$ と $b$ の少なくとも一方が合成数の場合を考えます．$a$ が合成数としましょう．すると $a$ は $n$ より小さい数なので帰納法の仮定により，素数の積に分解できる数です．これは $b$ が合成数の場合でも同様です．
以上により分解可能性が証明されました。
■
9.2 分解の一意性
定理 合成数を素数の積に分解する方法は，素因数の順序を無視すれば1通りである．
定理中の「素因数の順序を無視すれば」というのは，例えば合成数6は $2\times3$ という分解と $3\times2$ という分解の2通りが考えられますが，いずれも素因数2と3が1度ずつ用いられて合成されています．この場合，素因数分解の方法は1通りであるとして区別しません．$p,q,r,s$ をすべて異なる素数としてある合成数 $n$ が
\[n=pq=rs\]
という具合に書ければ，上の主張は偽ということになりますが，そうはならないことを以下で証明します．
証明
数学的帰納法で示します．
1° 1番小さい合成数4は，$4=2\times2=2^2$ で1通りです．
2° $n$ を合成数とし，$n$ より小さい合成数の分解の一意性は保証されているとします．このとき，$n$ が素因数分解として2通りの表現ができたとしましょう：
$n=p\,q\,r\cdot \cdots=p’q’r’\cdot \cdots$ (①)
ここで $p,q,r,\cdots$ や $p’,q’,r’,\cdots$ はすべて素数です．
まず，$p\neq p’$ でなければなりません．何故というに，$p=p’$ ならば，①の各辺を $p$ で割ると
\[\frac np=q\,r\cdot \cdots=q’r’\cdot \cdots\]
となりますが，$\dfrac np$ は $n$ より小さな数ですから帰納法の仮定により分解の方法は1通りです．即ち
\[q\,r\cdot \cdots=q’r’\cdot \cdots\]
の両辺は全く同じ素数の積となっており，$n$ の素因数分解が2通りあったということに反します．これで $p\neq p’$ であることがわかりました．同様にして，$p’$ は $q,\ r,\ \cdots$ のいずれとも異なります．
今 $p>p’$ であったとしておきます．
次に，$n$ から $p’q\,r\cdot\cdots$ を引いてみます．①の中辺と右辺は
\[(p-p’)q\,r\cdot\cdots=p'(q’r’\cdot\cdots-q\,r\cdot\cdots)\]
となります．右辺の先頭に素数 $p’$ がありますが，先ほど確認したように左辺の $q,r,\cdots$ のいずれの素数とも異なりますから $p-p’$ の約数となるしかありません．するとある数 $s$ を用いて
\[p-p’=p’s\]
と書けますが，この式より$p=p'(s+1)$ となって $p’$ が $p$ の約数になります．しかるにこれでは $p$ と $p’$ が異なる素数であるとしたことに矛盾してしまいます．
結局 $n$ の分解の方法が2通りあるという仮定がまずいということがわかり，証明が完了です．
■
このページで疑問は解決されましたか？
こちら から数学に関するご質問・ご要望をお寄せください。
高校数学[総目次]
高校数学ワンポイント