9.4 算術の基本定理

読者も既に知っているはずの素数に関する重要な事実がある: 全ての正整数は一意な素因数分解を持つ。つまり、正整数を素数の積として表す方法は一つしか存在しない。奇妙な性質を持つ神出鬼没な素数は整数の基本構成要素として使えてしまう。

実数を乗じる順番を変えても積の値は変わらないので、厳密に言えば素因数分解は一意でない。例えば、\(12\) を素数の積として表す方法は三つある:

\[ 12 = 2 \cdot 3 \cdot 3 = 2 \cdot 3 \cdot 2 = 3 \cdot 2 \cdot 2 \]

素因数分解の一意性は、この例で「\(12\) に等しい素数の積は、必ず一つの \(3\) と二つの \(2\) だけからなる」を意味する。つまり積に含まれる素数をソートすると定めれば、素因数分解は本当に一意になる。

この事実をさらに正確に表明しよう。整数の列が広義減少 (weakly decreasing) とは、任意の要素が次の要素以上であることを言う。この定義では長さ \(1\) の列と長さ \(0\) の列は広義減少となる点に注意してほしい。

定理 9.4.1[算術の基本定理 (fundamental theorem of arithmetic)]

任意の正整数は、素数からなる一意な広義減少列の積である。

例えば、\(75237393\) は次に示す素数の広義減少列の積である:

\[ (23,\ 17,\ 17,\ 11,\ 7,\ 7,\ 7,\ 3) \]

そして、積が \(75237393\) となる素数の広義減少列は他に存在しない¹。

\(1\) が素数だと定理 9.4.1 は成立しない点に注目してほしい。例えば、\(15\) は \(5\cdot 3\), \(\,5 \cdot 3 \cdot 1\), \(\,5 \cdot 3 \cdot 1 \cdot 1\), \(\ldots\) のいずれとも等しい。

前節で触れた素数の不規則性から考えると、素因数分解の一意性はある意味で奇妙に思える。仮に赤ん坊のころから知っていたとしても、この性質を証明なしに用いて構わないと思うのは間違いである。実は、素因数分解の一意性は \(\{ n + m \sqrt{-5} \; | \; n, m \in \mathbb{Z} \}\) などの整数に似た集合の多くで成り立たない (問題 9.25)。

算術の基本定理は素因数分解の一意性定理 (unique factorization theorem) とも呼ばれる。分かりやすい名前ではあるものの、神妙さは減る ── しかし素因数分解の一意性が非自明であるという事実はそうしてでも強調するだけの価値がある。

9.4.1 素因数分解の一意性の証明

算術の基本定理の証明は難しくないものの、いくつかの補助的な事実が必要になる。

補題 9.4.2

\(p\) が素数で \(p \; | \; ab\) なら、\(p \; | \; a\) または \(p \; | \; b\) が成り立つ。

補題 9.4.2 は素因数分解の一意性があれば直ちに従う: 積 \(ab\) に含まれる素数は \(a\) または \(b\) に含まれる素数のみと言える。しかし、この証明はズルである: 私たちはこれから素因数分解の一意性を証明するのに、それを使って補題を証明しては循環論法になる。代わりに最大公約数と線形結合の関係を使えば、循環論法を引き起こさない証明が得られる。

証明もし \(\operatorname{gcd}(a, p) = p\) なら \(a\) は \(p\) の倍数なので、補題は成り立つ。

そうでなければ \(\operatorname{gcd}(a, p) \neq p\) である。素数 \(p\) を割り切る整数は \(1\) と \(p\) 以外に存在しないから、このとき \(\operatorname{gcd}(a, p) = 1\) が成り立つ。\(\operatorname{gcd}(a, p)\) は \(a\) と \(p\) の線形結合なので、\(1 = sa + tp\) を満たす整数 \(s\), \(t\) が存在する。この両辺に \(b\) を乗じれば \(b = s(ab) + (tb)p\) を得る。つまり \(b\) は \(ab\) と \(p\) の線形結合である。\(p\) は \(ab\) と \(p\) の両方を割り切るから、その線形結合 \(b\) も割り切る。 ■

補題 9.4.2 は典型的な数学的帰納法で拡張できる:

補題 9.4.3

\(p\) を素数とする。\(p \; | \; a_{1}a_{2} \cdots a_{n}\) なら、\(p\) は何らかの \(a_{i}\) を割り切る。

これで算術の基本定理を証明する準備が整った。

定理 9.4.1 の証明定理 2.3.1 は任意の整数が素数の積で表せることを (整列原理を使って) 示す。よって、後は素数の積としての表現が一意だと示せばよい。

背理法で示す。素数の積としての表現が複数ある整数が存在すると仮定する。整列原理より、そういった整数の中に最小値が存在する。その最小値を \(n\) として、素数の積による二つの異なる表現を

\[ \begin{aligned} n &= p_{1} \cdot p_{2} \cdots p_{j} \\ &= q_{1} \cdot q_{2} \cdots q_{k} \end{aligned} \]

と定める。ここで二つの積は広義減少の順序で並んでおり、\(p_{1} \leq q_{1}\) とする。

もし \(q_{1} = p_{1}\) なら、\(n/q_{1}\) は素数の広義減少列の積としての異なる表現を二つ持つ:

\[ \begin{aligned} n/q_{1} &= p_{2} \cdots p_{j} \\ &= q_{2} \cdots q_{k} \end{aligned} \]

しかし \(n/q_{1} < n\) なので、これは \(n\) の最小性と矛盾する。よって \(p_{1} < q_{1}\) である。

\(p_{i}\) は広義減少なので、任意の \(p_{i}\) は \(q_{1}\) より小さい。一方で

\[ q_{1} \; | \; n \ \ \longleftrightarrow \ \ q_{1} \; | \; p_{1} \cdot p_{2} \cdots p_{j} \]

と補題 9.4.3 からは、\(q_{1}\) が何らかの \(p_{i}\) を割り切ると分かる。しかし、これは \(q_{1}\) が全ての \(p_{i}\) より大きい事実と矛盾する。 ■

長さ \(1\) の列の積は唯一の要素に等しく、長さ \(0\) の列の積は \(1\) と定義される。任意の素数 \(p\) は長さ \(1\) の列 \((p)\) の積に等しく、\(1\) (素数ではないのだった) は長さ \(0\) の列の積に等しい。これらの列は広義減少かつ一意である。 ↩︎