2.3 素因数分解

「\(1\) より大きい任意の整数は素数の積として一意¹に表せる」という事実は素因数分解定理 (prime factorization theorem)、素因数分解の一意性定理 (unique factorization theorem)、算術の基本定理 (fundamental theorem of arithmetic) などと呼ばれる。本講義でも当然のものとして利用してきたこの事実もまた、「成り立つのは当然と思って使っているのに、よく考えると明らかでない」数学的事実の一つである。素因数分解の一意性は第 9.4.1 項で証明する。ここでは \(1\) より大きい任意の整数が素数の積として表せることの整列原理を使った簡単な証明を示す (一意性は証明されない)。

証明 整列原理を使った背理法で証明する。

素数の積として表せない \(1\) より大きな整数を全て集めた集合を \(C\) とする。\(C\) が空でないと仮定して矛盾を導く。

\(C\) が空でないなら、整列原理より \(C\) には最小要素 \(n\) が存在する。この \(n\) は素数でない。なぜなら、任意の素数は一つの素数 (それ自身) の積であり、そういった整数は \(C\) に属さないからである。

よって \(n\) は二つの整数 \(a\), \(b\) の積であり、ここから \(1 < a, b < n\) が言える。つまり \(a\) と \(b\) は \(C\) の最小要素 \(n\) より小さいので \(a, b \notin C\) が分かる。言い換えれば、\(a\) は素数の積として \(p_{1} \cdots p_{k}\) と表され、\(b\) も素数の積として \(q_{1} \cdots q_{l}\) と表される。従って \(n = ab = p_{1} \cdots p_{k}q_{1} \cdots q_{l}\) もまた素数の積として表せる。これは \(n \in C\) と矛盾するので、\(C\) が非空という仮定は偽だと分かる。 ■