素因数分解の一意性とその証明について

更新 2021/03/07

素因数分解の一意性

全ての正の整数は素数の積として（順番を除いて）一意に表せる。

算術の基本定理とも呼ばれる重要な定理です。一見当たり前ですが実は当たり前ではありません。きちんと証明しようとするとけっこう大変です。

素因数分解の可能性

「素数」とは $1$ と自分自身以外の約数を持たない数のことです。

素因数分解が可能であることの証明は簡単です。当たり前のことをきちんと書いただけです。

証明

背理法で証明する。素因数分解不可能な正の整数が存在すると仮定する。その最小のものを $n$ とする。

素数（および $1$ ）はもちろん素因数分解可能なので $n$ は素数ではない。

よって， $n$ は $1$ より大きく $n$ より小さい約数を持つ。よって $n=ab$ ( $a,b$ は $1$ より大きく $n$ より小さい正の整数）と表せる。

最小性の仮定より $a$ と $b$ は素数の積で表せる。よって $n$ も素数の積で表せるので矛盾。

注： $1$ の素因数分解についてはいくつか流儀があるようなのですが，ここでは「 $0$ 個の素数の積」とみなすことにします。

一意性証明の必要性（自明じゃないよってこと）

続いて本題。素因数分解が一意であることを証明します。以下の補題を認めてしまえば簡単です。
ユークリッドの補題
素数
ppp
 が
ababab
 を割り切るなら，ppp
 は
aaa
 か
bbb
 の少なくとも一方を割り切る。
この補題，当たり前に見えますが実は自明ではありません。素数の定義を使ってきちんと証明するべき定理です。
高校生向けの多くの本，サイトがこの補題を暗黙のうちに使って素因数分解の一意性を証明していますが，よろしくありません。
実際，整数の世界でこの補題は成立しますが，
この補題が成立しないようなヤバい世界（集合）も存在します（例えば Z[−5]\mathbb{Z}[\sqrt{-5}]Z[−5​]）。素因数分解の一意性が成り立たない世界も存在するのです！
ということで，ユークリッドの補題については最後に考えるとして，ユークリッドの補題を認めた上で素因数分解の一意性を証明します。

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

ユークリッドの補題を繰り返し使うことで，

素数 $p$ が $a_1a_2\cdots a_n$ を割り切れるなら， $p$ が $a_1,\cdots, a_n$ の少なくとも一つを割り切ることが分かります。これを使って証明します。

証明

$N$ が二通りに素因数分解できたと仮定する：

$N=p_1p_2\cdots p_n=q_1q_2\cdots q_m$

（ $n\leq m$ ， $p_i$ や $q_i$ たちは同じものが複数あってもよい）

中辺は $p_1$ の倍数なので補題より $q_1$ から $q_m$ のいずれかが $p_1$ で割り切れる。 $q_1$ が $p_1$ の倍数としても一般性を失わない。ところが $p_1$ も $q_1$ も素数なので $p_1=q_1$ である。

以下同様に（適当に順番をつけることで） $p_2=q_2,\cdots, p_n=q_n$ が分かる。

$n <m$ のとき，もとの式より $1=q_{n+1}\cdots q_m$ となるがこれは不適。つまり $n=m$ となる。

以上により二通りの素因数分解は一致した。

ユークリッドの補題について

ユークリッドの補題は例えば以下の手順できちんと証明できます。

割り算（商と余り）がきちんと定義できること
ユークリッドの互除法が使えること
ベズーの定理が成立すること，つまり $(a,b)$ が互いに素なとき $ax+by=1$ を満たす整数 $(x,y)$ が存在すること
ユークリッドの補題が成立すること

それぞれのステップは難しくありませんが，全て書くと長くなるので省略します。

なお，一次不定方程式ax+by=cの整数解でべズーの定理を解説していますが，この記事にある証明方法はユークリッドの補題を使っています。循環論法を避けるためには上記の1，2のステップを踏む必要があります。

専門用語を使うと「ユークリッド整域なら単項イデアル整域，単項イデアル整域なら一意分解整域であることの証明」と同じ流れです。

何が当たり前で何が当たり前でないきちんと区別するのはけっこう大変です。

Tag:素数にまつわる覚えておくべき性質まとめ

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！