算術の基本定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

算術の基本定理（さんじゅつのきほんていり、英:fundamental theorem of arithmetic）とは「すべての自然数は素数であるか、素数の積としてただ一通りに表すことができる数である」という数論における定理である。例えば120は 2³×3×5 と素因数分解され、これ以外の素因数分解された形として表わすことはできない。なおここでは1は「0個の素因数の積」と考えることにする。

[編集] 証明

最初にこの定理を証明したのはユークリッドであるが、その完全な証明を著したのはカール・フリードリヒ・ガウスである。

すべての自然数が素数の積で表されることを証明するため、まず素数の積で表わせない自然数を仮定する。そのような数には最小の数があるはずであり、それをnとおく。nには上記の定義から1は当てはまらず、素数もその数単独の積であるので該当しない。したがってnは合成数で、 n=ab と表わすことができ、aとbはnより小さい自然数となる。aとbがnより小さく、nは「素数の積で表わせない自然数のうち最小の数」なので、aとbは素数の積で表わすことができる自然数である。するとabも素数の積で表わすことができる数となりnについての仮定に反する。これは背理法を用いた証明である。

素因数分解の一意性を示すため、素数pが自然数の積の形で表された数abを割り切ることができるならば、pはaもしくはbの約数であることを証明する。pがaの約数でなければpとaは互いに素であり、このことは整数x,yを用いて以下のように表される。

px + ay = 1

さらに両辺にbをかけることで pbx +aby = b 。この式の左辺はpで割り切れるので右辺もpで割り切れ、aがpで割り切れないときbがpで割り切れるということが示せた。

与えられた二つの「複数の素数の積」がそれぞれ等しいならば、一つ目の積の要素から素数pを選び出すことができる。このpは一つ目の積を割り切り、したがってもう一方の積も割り切る。これはpが二つ目の積の要素のうち少なくとも一つを割り切ることを示す。しかし積の要素はそれぞれ全て素数であるので、pは二つ目の積の要素の一つに等しくなければならない。ゆえにpを両方の積から消去してもそれらは互いに等しく、このような操作を続けることで両方の積の各要素は全てもう一方の積の要素のいずれかと等しいことが証明される。