人気ブログランキング | 話題のタグを見る

素因数分解の一意性の証明

正整数Aが素数ならば、Aの素因数分解はAで決まる。なので、Aが非素数の場合に、一意に分解できることを示せばいい。

A=B*C
A=B*D

であれば
C=D

この証明は簡単だ。両辺をBで割ると、

A/B=C
A/B=D

ゆえに、C=D

Bを素数とすると、
A=B(素数)*C
A=B(素数)*D

ここで、C=Dなので、合成数を同じ素数で割ると、同じ数が商として現れる。

Cについても、同じ議論が成り立つので、

C=E*F
C=E*G

ならば、F=Gなので、Eを素数として

A=B(素数)*E(素数)*F
A=B(素数)*E(素数)*G

F=G

さらに、Fについて同じ議論を繰り返してゆく。

A=B(素数)*E(素数)*F(素数)*H
A=B(素数)*E(素数)*F(素数)*I

ならば、H=I

正の整数は無限に分解できないので、どこかでこの連鎖は止まる。大文字表記のBCD・・をa1,a2・・と書き換えて、

A=a1*a2*・・an

と分解を表記できる。ai=素数であれば、

A=b1*b2*・・bn
であっても、すべてのaiは、なにがしかのblとなる。

これで、証明できたのではないか。
by tomoarrow | 2016-05-20 07:00 | モチーフについて | Comments(0)