素因数分解そいんすうぶんかいと算術さんじゅつの基本定理きほんていり

4.1仮定かてい

$p$p を素数そすうとし、$a,b$a,b を整数せいすうとする。$p\mid ab$p\mid ab とする。

4.2結論けつろん

である。

4.3証明しょうめい

$p\mid a$p\mid a なら結論けつろんは成立せいりつする。そこで $p\nmid a$p\nmid a とする。

$p$p は素数そすうであり、$p\nmid a$p\nmid a だから、$p$p と $a$a の最大公約数さいだいこうやくすうは 1 である。したがって、Bezout 表示ひょうじにより、ある整数せいすう $u,v$u,v が存在そんざいして

と書かける。

この両辺りょうへんに $b$b を掛かけると、

である。$p\mid upb$p\mid upb は明あきらかであり、仮定かてい $p\mid ab$p\mid ab から $p\mid vab$p\mid vab である。したがって $p$p は左辺さへんを割わり切きるので、$p\mid b$p\mid b である。□

5.1仮定かてい

$n$n を 2 以上いじょうの整数せいすうとする。

5.2結論けつろん

$n$n は素数そすうの積せきとして表あらわせる。また、その表あらわし方かたは順序じゅんじょを除のぞいて一意いちいである。

5.3証明しょうめい：存在そんざい

$n$n について数学的帰納法すうがくてききのうほうを使つかう。

$n$n が素数そすうなら、$n$n 自身じしんが素数そすうの積せきである。$n$n が素数そすうでないなら、$n$n は合成数ごうせいすうなので、

と書かける。帰納法きのうほうの仮定かていにより、$a,b$a,b はそれぞれ素数そすうの積せきに分わけられる。よって $n=ab$n=ab も素数そすうの積せきに分わけられる。

5.4証明しょうめい：一意性いちいせい

という二ふたつの素因数分解そいんすうぶんかいがあるとする。$p_1$p_1 は左辺さへんを割わり切きるので、右辺うへん $q_1{q}_2\cdots q_l$q_1q_2\cdots q_l も割わり切きる。

Euclid の補題ほだいを繰くり返かえし使つかうと、$p_1$p_1 は $q_j$q_j のどれかを割わり切きる。$q_j$q_j は素数そすうだから、$p_1=q_j$p_1=q_j である。

そこでこの共通きょうつうの素数そすうを両辺りょうへんから約やくす。同おなじ議論ぎろんを繰くり返かえすと、現あらわれる素数そすうは順序じゅんじょを除のぞいて一致いっちする。したがって素因数分解そいんすうぶんかいは一意いちいである。□