背理法の理解・整数問題（６）の解

　背理法の理解・整数問題（６）の解答例を示します。

問題（６）の解

　背理法で示す。

　「ある正整数aが複数通りに素因数分解される」と仮定して矛盾を導く。

このように仮定すると、

　　a = p(1)p(2)･･･p(n)　（p(1)≧p(2)≧･･･≧p(n), p(1),･･･,p(n)は素数）
　　　= q(1)q(2)･･･q(m)　（q(1)≧q(2)≧･･･≧q(m), q(1),･･･,q(m)は素数）

と書ける。

ここで、上式中、1番目からk-1番目までの素数が等しく、k番目で初めて違う

素数が現れたとする。

すなわち、

　　p(1)=q(1),･･･,p(k-1)=q(k-1), p(k)＞q(k)　または　p(k)＜q(k)

が成り立つ。

p(k)＞q(k)と仮定すると、

　　　　p(k)p(k+1)･･･p(n) = q(k)q(k+1)q(k+2)･･･q(m)

となるが、

p(k)とq(k)は、互いに素であることから、
p(k)はq(k+1)q(k+2)･･･q(m)の約数でなければならない。

同じように考えると、

p(k)とq(k+1)は、互いに素であるから、
p(k)はq(k+2)･･･q(m)の約数でなければならない。

p(k)とq(k+2)は、互いに素であるから、
p(k)はq(k+3)･･･q(m)の約数でなければならない。

・・・

p(k)とq(m-2)は、互いに素であるから、
p(k)はq(m-1)q(m)の約数でなければならない。

p(k)とq(m-1)は、互いに素であるから、
p(k)はq(m)の約数でなければならない。

結局、

　　p(k)≦q(m)≦q(k)

となり、p(k)＞q(k)と矛盾する。

p(k)＜q(k)と仮定しても同様の矛盾に到達する。

したがって、素因数分解の表し方は1通りであることが示された。