算術の基本定理

証明

この定理を最初に証明したのはユークリッドである。最初の詳細で正しい証明は、カール・フリードリヒ・ガウスの Disquisitiones Arithmeticae に記載されている。

この定理はどこでも成り立つと思っている人がいるかもしれません。しかし、この定理は、代数的整数のような、より一般的な数の体系では成り立ちません。このことは、1843年にErnst KummerがFermatの最終定理に関する研究で初めて言及しました。それについての詳細は：代数的整数論をお読みください。

この証明は2つの部分から構成されています。まず、すべての数は素数の積として書くことができることを示し、次に、ある数を2回目に素数の積として書いた場合、素数の2つのリストは同じでなければならないことを示します。

証明の最初の部分

私たちは、1より大きいすべての数が素数の積として書けなければ、ある種の不可能性に行き着くことを示しました。その結果、すべての数が素数の積として書けることは真実でなければならないという結論に達しました。

では、誰かが「素数の積として書けない1以上の正の整数を知っている」と言ったらどうなるでしょうか。この場合、私たちはその人に、素数の積として書けない1以上の数をすべて挙げてもらいます。その中で一番小さい数をnとします。もちろん、このnは1ではありません。なぜなら、素数は1つの素数、つまり自分自身の「積」であるからです。つまり、数の積でなければなりません。したがって

n = ab

ここで，aとbはともに正の整数で，もちろんnよりも小さい。しかし，nは素数の積として書けない最小の数である。ということは、aとbはどちらもnより小さいので、素数の積として書くことができるはずです。

n = ab

は、素数の積としても書くことができます。これは、nを素数の積として書くことはできないと言ったので、不可能なことです。

これで、定理の最初の部分が成立しない場合に存在する不可能性を示しました。このようにして、私たちは定理の最初の部分を証明しました。

証明の第二部

今度は、1より大きい正の数を素数の積として書く方法が1つしかないことを証明しなければなりません。

そのためには、次のようなレンマを利用します。素数pが積abを分割する場合、aを分割するかbを分割するか、というものです（ユークリッドのレンマ）。まず、このレンマを証明します。さて、pがaを割らないと仮定します。そうすると、pとaは共起であり、次のような整数xとyが存在しなければならないというベゾウトの恒等式が成り立ちます。

px + ay = 1となります。

すべてにbをかけると

pbx + aby = bです。

つまり、左辺にはpで割り切れる2つの項があり、右辺の項もpで割り切れることになります。これで、pがaを割り切れないなら、bを割り切れるはずだということが証明されました。

ここでは、1より大きい整数を素数の積として1通りしか書けないことを証明します。結果が同じになる素数AとBの2つの積を考えます。最初の積Aから任意の素数pを取ります。それはAを割るので、Bも割ることになります。先ほど証明したレンマを何度か使うと、pはBの少なくとも1つの因子bを割らなければならないことがわかります。しかし、因子はすべて素数なので、bも素数です。そこで、Aをpで割り、Bもpで割ってみると、A* = B*のような結果が得られます。この場合も、最初の積A*から素数pを取り出し、それが積B*のある数に等しいことがわかります。このようにして続けていくと、最後には2つの積の素因数が全く同じでなければならないことがわかります。これは、正の整数を素数の積として書くことができる唯一の方法であることを証明しています。