１．自然数の分類

　２以上の自然数ｎはｎ＝１×ｎと表す事が出来る。つまりこれらの自然数は最低１とｎという２つの約数を持つ。素数とは１とｎ以外に約数を持たない数の事を言い、合成数とは３つ以上の約数を持つ数の事を指す。また１とn以外の約数を真の約数と呼ぶ。つまり自然数は

• １
  
• 素数→２つの約数を持つ
  
• 合成数→３つ以上の約数を持つ

２．素数

　正の整数Ｐにおいて、割り切れる正の整数が２つ（１とその数自身）しかない場合、Ｐは素数と判断出来る。小さい素数を上げてみると２、３、５、７、１１、１３、１７、１９、２３、２９、３１、３７、４１、４３、４７、５１という具合になる。素数は無限に存在する。この証明は約２３００年前にユークリッド著『原論』においてなされている。証明の概要は以下の通りである。

　ｎ個の素数ｐ_１、ｐ_２、ｐ_３、・・・、ｐ_ｎが与えられた時、これら以外に素数がある事を示す。
ｑ＝ｐ_１×ｐ_２×ｐ_３×・・・×ｐ_ｎ＋１
とする。が素数の場合、ｑはｐ_１、・・・ｐ_ｎのいずれの数よりも大きく、ｐ_１、・・・ｐ_ｎ以外の素数と判定できる。
ｑが合成数ならば、ｑを割る最小の真の約数をｒとする。するとｒは素数である。なぜならｒの真の約数ｓがあったならば
ｓ｜ｒ、ｒ｜ｑ　　　∴ｓ｜ｑ、ｓ＜ｒ
となり、ｒが最小の真の約数である事に反する。よってｒは素数だが、ｒはｐ_１、・・・ｐ_ｎのどれとも等しくない。それは、ｑをｐ_ｉで割ると必ず１余るので、ｐ_ｉはｑの約数ではないからである。ｑが素数でも合成数でもｐ_１、・・・ｐ_ｎ以外の素数が存在するのである。予って素数は無限に存在する事が証明された。

３．素因数分解の一意性

　素因数分解は合成数を素数の積で表す事であるが、素因数分解の一意性とは、ある合成数ａを素因数分解した時にａは１通りのみの素数の積でしか表せないという事を意味する。この証明は次の通りである。

自然数ａとｂの最大公約数が１の時、つまりａとｂには共通な約数が１しかない時、ａとｂは互いに素という。
この時（ａ，ｂ）＝１だから、１＝ｘａ＋ｙｂとなる整数ｘ，ｙはユークリッドの互除法を利用すると求める事が出来る。（ａ，ｂ）＝１、ａ｜ｂ・ｃのときａ｜ｃとなることが以下のように表せる。
ｘａ＋ｙｂ＝１
この式を満たす整数ｘ，ｙは存在するのでこの式の両辺にｃを掛けると
ｘａｃ＋ｙｂｃ＝ｃ
となる。ａｃもｂｃもａで割れるので左辺はａで割れる。つまりａ｜ｃが成立したといえる。
次にａが２通りに素因数分解されたとして
ａ＝ｐ_１×ｐ_２×ｐ_３×・・・×ｐ_ｎ＝ｑ_１×ｑ_２×ｑ_３×・・・×ｑ_ｍ、　　ｐ_１≦ｑ_１≦ｑ_２≦・・・≦ｑ_ｍ
となったとする。ｐ_１とｑ_１が異なれば、ｐ_１もｑ_１も素数であるから（ｐ_１，ｑ_１）＝１となる。ｐ_１はａを割るから、ｐ_１はｑ_１×（ｑ_２ｑ_３・・・ｑ_ｍ）を割る。よって、ｐ_１はｑ_２ｑ_３・・・ｑ_ｍを割る。同様にして、ｐ_１＜ｑ_２よりｐ_１｜ｑ_３・・・ｑ_ｍとなる。これを続けて行うとｐ_１｜１となるため矛盾が生じる。つまりｐ_１はｑ_１と等しくなければいけない。よって両辺をｐ_１で割り
ｐ_２×ｐ_３×・・・×ｐ_ｎ＝ｑ_２×ｑ_３×・・・×ｑ_ｍ
が得られる。同様にｐ_２＝ｑ_２、ｐ_３＝ｑ_３、・・・ｐ_ｎ＝ｑ_ｍとなる。両辺をこれらの素数で割っていくと必ず１となる。よって、ある合成数ａを素因数分解した時にａは１通りのみの素数の積でしか表せないという事が証明できた。

Yahoo! Japan

Yahoo! Deutschland

This page hosted by Get your own Free Homepage