背理法を用いない素因数分解の一意性の証明

自然数に0を含める.𝐍を自然数全体の集合,𝐙を整数全体の集合とする.

定義 1.

整数a,bに対してa=bcとなる整数cが存在するとき,ab倍数とよび,ba約数とよぶ.a,bに共通する倍数のことをa,b公倍数という.a,bの正の公倍数のうち,最も小さなものをa,b最小公倍数という.また,a,bに共通する約数のことをa,b公約数という.a,bの公約数のうち,最も大きなものをa,b最大公約数という.整数a,bの最大公約数が1であるとき,a,b互いに素であるという.

定理 1 (除法の定理).

整数aと正の整数bに対してa=bq+r(0r<b)を満たす整数q,rが一意的に存在する.

𝐙の部分集合A={n𝐙q𝐙n=a-bq}に対して,𝐍Aは空でないので,最小元rが存在する.rの最小性よりrより小さな元は𝐍Aの元ではない.r𝐍よりr0rAよりあるq𝐙が存在してr=a-bqと表せる.このとき,r-b=a-b(q+1)Aだが,r-brより小さいので,𝐍Aの元ではない.ゆえにr-b𝐍.よってr-b<0,すなわちr<b.以上より0r<b.次に一意性を示す.a=bq+r(0r<b)a=bq+r(0r<b)とすると,bq+r=bq+rr-r=b(q-q)より,r-rbの倍数である.-b<-r0より-b<r-r<bが成り立つ. -bより大きくbより小さいbの倍数は0しかないので r-r=0,すなわちr=r.また,b(q-q)=0かつb0よりq=q

定義 2.

整数aと正の整数bに対し,前命題によって定まるqabで割ったときのr余りという.余りが0のとき,ab割り切れるといい,baで表す.

定理 2 (公倍数は最小公倍数の倍数).

a,bの最小公倍数をlとする.ma,bの公倍数とするとき,mlの倍数である.

mlで割る.すなわち,m=lq+r(0r<l)を満たす整数l,rをとる.r=m-lqにおいて,mla,bの公倍数だから,ra,bの公倍数である.r<lであり,lが最小の公倍数であることより,r=0が成り立つ.すなわち,mlの倍数である.

定理 3 (公約数は最大公約数の約数).

a,bの最大公約数をgとする.da,bの公約数とするとき,dgの約数である.

d,gの最小公倍数をlとする.l=gを示せば,gdの倍数,すなわち,dgの約数であることが示せる.公倍数の定義よりgl.また,adの倍数かつgの倍数より,d,gの公倍数である.よって,前命題よりlaの倍数.同様にすればlbの倍数.したがって,la,bの公約数.gは最大公約数だから,lg.ゆえにl=g

定理 4.

整数a,bに対してga,bの最大公約数とすると,整数a,bを用いてa=ag,b=bgと表せる.このとき,a,bは互いに素である.

a,bの公約数をdとすると,dga,bの公約数になる.gは最大の公約数だから,d=1.ゆえに,a,bは互いに素.

定理 5.

整数 a,bに対して,la,bの最小公倍数,ga,bの最大公約数とするとき,ab=lgが成り立つ.

前命題より,互いに素な整数a,bを用いてa=ag,b=bgと表せる.このとき,l=abgとすると,l=ab=abより,la,bの公倍数である.公倍数は最小公倍数の倍数だから,l=elを満たす整数eが存在する. l=abよりab=elであり,laで割り切れるので,beで割り切れる.同様にl=abよりab=elであり,lbで割り切れるので,aeで割り切れる.すなわち,ea,bの公約数である.a,bは互いに素だからe=1.すなわち,l=l.ゆえに l=abg.以上よりab=(ag)(bg)=(abg)g=lgが成り立つ.

定理 6.

整数a,bが互いに素でかつacbで割り切れるとき,cbで割り切れる.

a,bが互いに素であることより, aba,bの最小公倍数.また,acbで割り切れるから,a,bの公倍数.したがって,acabの倍数.ゆえに,acbで割り切れる.

定義 3 (素数).

1より大きい整数p1p以外に約数を持たないとき,p素数とよぶ.

定理 7.

pを素数とする.整数apで割り切れないならば,a,pは互いに素である.

対偶を示す.a,pが互いに素でないとすると,a,p1より大きい公約数dをもつ.pは素数だからその約数は1またはpなので,p=d.よってapで割り切れる.

定理 8 (数の元素).

a,bを整数,pを素数とする.abpで割り切れるならば,apで割り切れるか,bpで割り切れる.

abpで割り切れるとする.apが割り切れるならば,主張は正しい.apで割り切れないとき,前命題より,apは互いに素である.abpで割り切れるので,定理 6よりbpで割り切れる.

定理 9.

nを正の整数とする.n個の整数の積が素数pで割り切れるとき,そのどれかはpで割り切れる.

nについての帰納法.1個の整数の積がpで割り切れれば,その1つの整数がpで割り切れている.n個未満の整数の積がpで割り切れると,そのどれかがpで割り切れるとする.n個の整数a1,a2,,anに対してa1a2anpで割り切れるとする.a1pで割り切れるならば主張は正しい.a1pで割り切れないとき,前命題よりa2anpで割り切れる.帰納法の仮定よりa2,,anのどれかはpで割り切れる.

定理 10 (素因数分解の可能性).

1より大きい任意の正の整数nは,素数の積である.ここで,素数そのものも素数の積とみなす.

nについての帰納法.n=2のとき,2は素数なので主張は正しい.n>2として,1より大きくnより小さな整数が素数の積であると仮定する.nが素数のとき主張は正しい.nが素数でないとき,1より大きくnより小さい正の整数a,bが存在してn=abと表せる.帰納法の仮定より,a,bは素数の積だからnも素数の積である.

定理 11 (素因数の存在).

1より大きい整数nに対して,ある素数pと整数mが存在してn=pmと表せる.

前命題よりnは素数の積で表せるので,主張は正しい.

定義 4 (素因数リスト).

1より大きい正の整数nに対して,n=p1p2pr,p1p2prを満たす素数の列(p1,p2,,pr)𝐙rを,n素因数リストと呼ぶ.素因数分解の可能性より,素因数リストは少なくとも1つ存在する

定理 12 (素数の素因数リスト).

素数pに対して,pの素因数リストは(p)であり,一意的である.

(p1,p2,,pn)pの素因数リストだとするとp=p1p2pnと表せる.各pipの約数なので,1pである.しかし,piは素数なのでpi=p.すなわちp=pn.よってn=1となり,pの素因数リストは(p)しかありえない.

定理 13 (素因数分解の一意性).

n1より大きい整数とする.nの素因数リストは一意的である.すなわち,2つの列(p1,p2,,pr),(q1,q2,,qs)が共にnの素因数リストのとき,これらは等しい.つまり,r=sかつ任意の1irに対してpi=qiが成り立つ.

n=2のときは前命題より素因数リストは(2)しかない.n>2として,1より大きくnより小さい整数の素因数リストが一意的だと仮定する.nが素数の場合は,前命題より(n)が唯一つの素因数リストになる.nが素数でないとき,pnの最小の素因数とすると,n=pmを満たす1より大きくnより小さな正の整数mが存在する.nの素因数リスト(p1,p2,,pr)を任意にとると,n=p1p2pr(p1p2pr)と表せて,pは素数だから定理 8より,pp1,p2,,prのいずれかを割り切り,pが最小の素因数であることより,p1=p,p2pr=mである.よって,nの素因数リストを任意にとると,必ず最初の素数はpになる.次に(q1,q2,,qs)nの素因数リストとすると,q1=pかつ(p2,p3,,pr),(q2,q3,,qs)mの素因数リストだから,帰納法の仮定よりこれらは等しい.以上よりn2つの素因数リストは等しい.

コメントする