素因数分解の一意性（算術の基本定理）

\(2\) 以上の自然数に対する数学的帰納法で示す.

\(n=2\) のとき, \(2\) は素数であるから一意的な表示 \(2\) を持つ.

\(n\) を \(3\) 以上の自然数として
\(2\leq k\leq n-1\) なる自然数 \(k\) について素因数分解の一意性が成立すると仮定する.
\(n\) が素数ならば, それ自体が一意的な表示である.
\(n\) が合成数ならば, \(p\mid n\) となる素数 \(p\) が存在する.
よって, 自然数 \(n^\prime\) を用いて \(n=pn^\prime\) と書けるが, \(2\leq n^\prime<n\) なので \(n^\prime\) は(一意的に)素数の積で表せる.
素数の積 \(n^\prime\) に素数 \(p\) をかけているので \(n\) が素数の積で表せることが分かる.
\(p_1,\ p_2,\ \ldots\ ,p_l,\ q_1,\ q_2,\ \ldots\ ,q_m\) なる素数(重複したものがあっても良い)を用いて \[n=p_1p_2\cdots p_l=q_1q_2\cdots q_m\] と２通りに書けたとする.
\(p_1\mid n\) なので, ユークリッドの補題より, ある \(j\) が存在して \(p_1\mid q_j\) となる.
番号を付け替えて, \(q_1=p_1\) となるようにして, \(p_1p_2\cdots p_l=q_1q_2\cdots q_m\) の両辺を \(p_1\) で割ると \(p_2\cdots p_l=q_2\cdots q_m\).
\(p_1\geq 2\) であるから \(2\leq p_2\cdots p_l < n\) であるが,
帰納法の仮定より \(p_2\cdots p_l=q_2\cdots q_m\) に対して素因数分解の一意性が成立するので \(l=m\) であり,
番号を付け替えると \(p_2=q_2, \ldots, p_l=q_l\) と出来る.
結局 \(p_1=q_1, p_2=q_2, \ldots, p_l=q_l\) であり, 素因数分解が一意的であることが分かった.