素因数分解の一意性を証明する。
①除法の原理
②ベズーの補題
③ユークリッドの補題
④素因数分解の一意性
①【除法の原理】
「二つの自然数nおよびm≠0に対してある自然数aおよびbが存在して
n=am+b (0 ≤b<m) が成立する」
===============================
②【ベズーの補題】
aとbを0でない整数とし、dをそれらの最大公約数とする。このとき整数xとyが存在して、ax+by=dとなる。
===============================
【証明】
与えられた 0 でない整数 a と b に対して、x と y を整数として ax + by がとりうる整数の集合 S について、S の任意の要素 u, v および整数 k に対して u + v, ku は S に含まれる。
実際u,vがu= ax[1]+by[1], v=ax[2]+by[2]と書ければ、
u+v=a(x[1]+ x[2])+b(x[2]+y[2])∈S,
ku=a(kx[1])+b(ky[1])∈Sである。
符号をかえれば u-v∈Sも同様にいえることがわかる。
今Sに含まれる正の整数のうち最小の数をhとする。するとSの要素はすべてhの倍数になっている。
というのは、もしhの倍数で表せない数mが存在すると仮定するとmをhで割った商をq、0でない余りをrと置いて
m=qh+r すなわち r =m-qhと書ける。
仮定より m∈ S およびh∈S, qh∈Sからr∈S。
r は割り算の余りなので割る数hより小さく、 これはhがSの最小の数であるという仮定に反する。すなわち S の要素はすべてhの倍数になっている。
ax+byの式でx=1,y=0を代入すればaとなるから、a∈S、同様にb∈S。 ということは、a,bはともにhの倍数であり、hはa,bの公約数である。したがってa, bの最大公約数g以下であるからh≦ g。……(1)
また a,bはgの倍数だから、a=a'g, b=b'g と置いて、
ax+by=(a'x+b'y)gとなり、Sの要素はgの倍数である。
特にh∈Sもgの倍数だからh≧g。……(2)
(1)(2)よりh=g、すなわち、
ax+by=g（gはa,b の最大公約数）
を満たすx, yが存在する。
【証明終】
===============================
③【ユークリッドの補題】
素数pがabを割り切るなら，
pはaかbの少なくとも一方を割り切る。
===============================
【ベズーの補題による証明】
ベズーの補題を利用した証明をする。ベズーの補題によれば、x, y が互いに素な整数であるなら（x, y の最大公約数が 1 であるなら）、
rx+sy=1…(1)
を満たすような整数 r, s が存在する。
a, c が互いに素であり、かつ c|ab であるとすれば、ベズーの等式 (1) より、以下の等式を得る。
rc+sa=1…(2)
(2) の両辺に b を掛ければ
rcb+sab=b…(3)となる。
(3) の左辺の第一項はcで割り切れ、第二項は ab で割り切れるので仮定よりcでも割り切れる。従ってそれらの和もcで割り切れるから c|b が成り立つ。
これは上述のユークリッドの補題の拡張になっている。
【証明終】
ユークリッドの補題を繰り返し使うことで，
素数 p が a[1]a[2]⋯a[n] を割り切れるなら，p が a[1],⋯,a[n] の少なくとも一つを割り切ることが分かります。これを使って証明します。
===============================
④【素因数分解の一意性】
「任意の正整数は、1 を除いて、一つまたはそれ以上の素数の積として（因子の順番の違いを除いて）ただ一通りに表すことができる」
===============================
【証明】
Nが二通りに素因数分解できたと仮定する：
N=p[1]p[2]⋯p[n]=q[1]q[2]⋯q[m]
（n≤m，p[i]やq[i]たちは同じものが複数あってもよい）
中辺はp[1]の倍数なので補題よりq[1]からq[m]のいずれかがp[1]で割り切れる。q[1]がp[1]の倍数としても一般性を失わない。ところがp[1]もq[1]も素数なのでp[1]=q[1]である。
以下同様に（適当に順番をつけることで）p[2]=q[2],⋯,p[n]=q[n]が分かる。
n<mのとき，もとの式より 1=q[n+1]⋯q[m]となるがこれは不適。つまりn=mとなる。
以上により二通りの素因数分解は一致した。
【証明終】
(2021/2/27)
