2

素因数分解の一意性

1175
0

素因数分解とは

素因数分解とは,ある自然数をいくつかの素数の積で表すことである。現在は中学3年生で学習するようである。高等学校でも,数学Aの「整数の性質」で再考するが,詳細は明記されていない。

素因数分解の一意性

学生はあまり意識しないが,素因数分解は積の順序を除けばただ1通りで表すことができる。実は明らかではなく,教科書を見ても「よく知られている」と書かれてあるだけである。ここでは,その事実を証明してみよう。

記号

Nを自然数全体の集合,Zを整数全体の集合とする。xNとある場合には,「xは自然数である」という意味である。

素因数分解の一意性を証明するために,次の補題を準備する。

ユークリッドの補題

pが素数  p>1かつa,bZに対して,abpの倍数ならば,aまたはbpの倍数

()
 pを素数とし,abpの倍数とする。a,pの最大公約数をgとすると,pは素数なので,g=pまたはd=1である。g=pのとき,apの倍数。d=1のときは,あるx,yZが存在して,ax+py=1。両辺b倍すると,b=abx+bpyとなるが,abxpの倍数なので,bpの倍数となる。

()
 dpの正の約数とすると,あるZが存在して,p=d()
 dpの倍数であるから,仮定より,またはdpの倍数である。

  • pの倍数であるから,あるxZが存在して,=px。(★)より,p=pxd すなわち xd=1を得る。d>0なのでd=1
  • dpの倍数であるから,あるyZが存在して,d=py。(★)より,p=py すなわち y=1を得る。(★)から>0がわかるので,=1。  d=p

以上より,pの正の約数は1またはpであるから,pは素数である。

この補題を利用すると,次の定理が証明できる。

素因数分解の一意性

任意のaNに対して,ある素数piが存在して
a=p1pn
と(積の順序を除いて)一意的に表すことができる。

【素因数分解可能性】
 a=1のときは,0個の素数の積で表せると考えればよいので,以下a>1としよう。
素数の積で表せない1より大きい自然数が存在すると仮定する。最小性原理により,そのような最小のaNがとれる。aは素数ではないので,1<b,c<aを満たすb,cNが存在して,a=bcaの最小性により,b,cは素数の積に分解できるから,aもそれらの積で表すことができる。

【一意的】
 2通りの素数の積で表せる自然数が存在すると仮定する。このような自然数をaとする。aが素数pi,qiを用いて
a=p1pm=q1qn(mn)
と表せているとしよう。q1qnp1で割り切れるので,p1q1の約数としても一般性を失わない。これを繰り返してp2=q2,,pm=qmとなる。qiは素数であるから,pi=qi(1im)であることがわかる。もとの式より,m<nならば
1=qm+1qn
となり不適。よって,m=nである。

投稿日:2021318
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 素因数分解とは
  2. 素因数分解の一意性