素因数分解の一意性
素因数分解とは
素因数分解とは，ある自然数をいくつかの素数の積で表すことである。現在は中学3年生で学習するようである。高等学校でも，数学Ａの「整数の性質」で再考するが，詳細は明記されていない。
素因数分解の一意性
学生はあまり意識しないが，素因数分解は積の順序を除けばただ1通りで表すことができる。実は明らかではなく，教科書を見ても「よく知られている」と書かれてあるだけである。ここでは，その事実を証明してみよう。
$\N$を自然数全体の集合，$\Z$を整数全体の集合とする。$x \in \N$とある場合には，「$x$は自然数である」という意味である。
素因数分解の一意性を証明するために，次の補題を準備する。
$p$が素数 $\Longleftrightarrow$ $p > 1$かつ$a,b \in \Z$に対して，$ab$が$p$の倍数ならば，$a$または$b$は$p$の倍数
($\Longrightarrow$)
$p$を素数とし，$ab$を$p$の倍数とする。$a, p$の最大公約数を$g$とすると，$p$は素数なので，$g=p$または$d=1$である。$g=p$のとき，$a$は$p$の倍数。$d=1$のときは，ある$x, y \in \Z$が存在して，$ax+py=1$。両辺$b$倍すると，$b = abx + bpy$となるが，$abx$は$p$の倍数なので，$b$も$p$の倍数となる。
($\Longleftarrow$)
$d$を$p$の正の約数とすると，ある$\ell \in \Z$が存在して，$p = \ell d \quad \cdots (★)$
$\ell d$は$p$の倍数であるから，仮定より，$\ell$または$d$は$p$の倍数である。
- $\ell$は$p$の倍数であるから，ある$x \in \Z$が存在して，$\ell = px$。(★)より，$p = pxd$ すなわち $xd = 1$を得る。$d > 0$なので$d = 1$。
- $d$は$p$の倍数であるから，ある$y \in \Z$が存在して，$d = py$。(★)より，$p = \ell py$ すなわち $\ell y = 1$を得る。(★)から$\ell > 0$がわかるので，$\ell = 1$。 $\therefore \ d = p$
以上より，$p$の正の約数は$1$または$p$であるから，$p$は素数である。
この補題を利用すると，次の定理が証明できる。
任意の$a \in \N$に対して，ある素数$p_{i}$が存在して
$$
a = p_{1} \cdots p_{n}
$$
と（積の順序を除いて）一意的に表すことができる。
【素因数分解可能性】
$a=1$のときは，0個の素数の積で表せると考えればよいので，以下$a>1$としよう。
素数の積で表せない1より大きい自然数が存在すると仮定する。最小性原理により，そのような最小の$a \in \N$がとれる。$a$は素数ではないので，$1 < b, c < a$を満たす$b, c \in \N$が存在して，$a = bc$。$a$の最小性により，$b, c$は素数の積に分解できるから，$a$もそれらの積で表すことができる。
【一意的】
2通りの素数の積で表せる自然数が存在すると仮定する。このような自然数を$a$とする。$a$が素数$p_{i}, q_{i}$を用いて
$$
a = p_{1} \cdots p_{m} = q_{1} \cdots q_{n} \quad (m \leq n)
$$
と表せているとしよう。$q_{1} \cdots q_{n}$は$p_{1}$で割り切れるので，$p_{1}$を$q_{1}$の約数としても一般性を失わない。これを繰り返して$p_{2} = q_{2}, \ldots , p_{m} = q_{m}$となる。$q_{i}$は素数であるから，$p_{i} = q_{i}$($1 \leq i \leq m$)であることがわかる。もとの式より，$m< n$ならば
$$
1 = q_{m+1} \cdots q_{n}
$$
となり不適。よって，$m = n$である。
