背理法を用いない素因数分解の一意性の証明

自然数に $0$ を含める． $\mathbf{N}$ を自然数全体の集合， $\mathbf{Z}$ を整数全体の集合とする．

定義 1.

整数 $a, b$ に対して $a=bc$ となる整数 $c$ が存在するとき， $a$ を $b$ の倍数とよび， $b$ を $a$ の約数とよぶ． $a, b$ に共通する倍数のことを $a, b$ の公倍数という． $a, b$ の正の公倍数のうち，最も小さなものを $a, b$ の最小公倍数という．また， $a, b$ に共通する約数のことを $a, b$ の公約数という． $a, b$ の公約数のうち，最も大きなものを $a, b$ の最大公約数という．整数 $a, b$ の最大公約数が $1$ であるとき， $a, b$ は互いに素であるという．

定理 1 (除法の定理).

整数 $a$ と正の整数 $b$ に対して $\begin{matrix} a = b q + r (0 ≦ r < b) \end{matrix}$ を満たす整数 $q, r$ が一意的に存在する．

$\mathbf{Z}$ の部分集合 $\begin{matrix} A = {n \in 𝐙 ∣ \exists q \in 𝐙 n = a - b q} \end{matrix}$ に対して， $\mathbf{N}\cap A$ は空でないので，最小元 $r$ が存在する． $r$ の最小性より $r$ より小さな元は $\mathbf{N}\cap A$ の元ではない． $r\in\mathbf{N}$ より $r\geqq 0$ ． $r\in A$ よりある $q\in\mathbf{Z}$ が存在して $\begin{matrix} r = a - b q \end{matrix}$ と表せる．このとき， $\begin{matrix} r - b = a - b (q + 1) \in A \end{matrix}$ だが， $r-b$ は $r$ より小さいので， $\mathbf{N}\cap A$ の元ではない．ゆえに $r-b\neq\mathbf{N}$ ．よって $r-b<0$ ，すなわち $r<b$ ．以上より $0\leqq r<b$ ．次に一意性を示す． $\begin{matrix} a & = b q + r (0 ≦ r < b) \\ a & = b q^{'} + r^{'} (0 ≦ r^{'} < b) \end{matrix}$ とすると， $\begin{matrix} b q + r & = b q^{'} + r^{'} \\ r - r^{'} & = b (q^{'} - q) \end{matrix}$ より， $r-r^{\prime}$ は $b$ の倍数である． $-b<-r\leqq 0$ より $\begin{matrix} - b < r^{'} - r < b \end{matrix}$ が成り立つ． $-b$ より大きく $b$ より小さい $b$ の倍数は $0$ しかないので $r-r^{\prime}=0$ ，すなわち $r=r^{\prime}$ ．また， $b(q^{\prime}-q)=0$ かつ $b\neq 0$ より $q=q^{\prime}$ ．

定義 2.

整数 $a$ と正の整数 $b$ に対し，前命題によって定まる $q$ を $a$ を $b$ で割ったときの商， $r$ を余りという．余りが $0$ のとき， $a$ は $b$ で割り切れるといい， $b\mid a$ で表す．

定理 2 (公倍数は最小公倍数の倍数).

$a, b$ の最小公倍数を $l$ とする． $m$ を $a, b$ の公倍数とするとき， $m$ は $l$ の倍数である．

$m$ を $l$ で割る．すなわち， $\begin{matrix} m = l q + r (0 ≦ r < l) \end{matrix}$ を満たす整数 $l, r$ をとる． $r=m-lq$ において， $m$ と $l$ は $a, b$ の公倍数だから， $r$ も $a, b$ の公倍数である． $r<l$ であり， $l$ が最小の公倍数であることより， $r=0$ が成り立つ．すなわち， $m$ は $l$ の倍数である．

定理 3 (公約数は最大公約数の約数).

$a, b$ の最大公約数を $g$ とする． $d$ を $a, b$ の公約数とするとき， $d$ は $g$ の約数である．

$d, g$ の最小公倍数を $l$ とする． $l=g$ を示せば， $g$ は $d$ の倍数，すなわち， $d$ は $g$ の約数であることが示せる．公倍数の定義より $g\leqq l$ ．また， $a$ は $d$ の倍数かつ $g$ の倍数より， $d, g$ の公倍数である．よって，前命題より $l$ は $a$ の倍数．同様にすれば $l$ は $b$ の倍数．したがって， $l$ は $a, b$ の公約数． $g$ は最大公約数だから， $l\leqq g$ ．ゆえに $l=g$ ．

定理 4.

整数 $a, b$ に対して $g$ を $a, b$ の最大公約数とすると，整数 $a^{\prime},b^{\prime}$ を用いて $\begin{matrix} a = a^{'} g, b = b^{'} g \end{matrix}$ と表せる．このとき， $a^{\prime},b^{\prime}$ は互いに素である．

$a^{\prime},b^{\prime}$ の公約数を $d$ とすると， $d g$ は $a, b$ の公約数になる． $g$ は最大の公約数だから， $d=1$ ．ゆえに， $a^{\prime},b^{\prime}$ は互いに素．

定理 5.

整数 $a, b$ に対して， $l$ を $a, b$ の最小公倍数， $g$ を $a, b$ の最大公約数とするとき， $\begin{matrix} a b = l g \end{matrix}$ が成り立つ．

前命題より，互いに素な整数 $a^{\prime},b^{\prime}$ を用いて $\begin{matrix} a = a^{'} g, b = b^{'} g \end{matrix}$ と表せる．このとき， $l^{\prime}=a^{\prime}b^{\prime}g$ とすると， $l^{\prime}=ab^{\prime}=a^{\prime}b$ より， $l^{\prime}$ は $a, b$ の公倍数である．公倍数は最小公倍数の倍数だから， $l^{\prime}=el$ を満たす整数 $e$ が存在する． $l^{\prime}=ab^{\prime}$ より $\begin{matrix} a b^{'} = e l \end{matrix}$ であり， $l$ は $a$ で割り切れるので， $b^{\prime}$ は $e$ で割り切れる．同様に $l^{\prime}=ab^{\prime}$ より $\begin{matrix} a^{'} b = e l \end{matrix}$ であり， $l$ は $b$ で割り切れるので， $a^{\prime}$ は $e$ で割り切れる．すなわち， $e$ は $a^{\prime},b^{\prime}$ の公約数である． $a^{\prime},b^{\prime}$ は互いに素だから $e=1$ ．すなわち， $l=l^{\prime}$ ．ゆえに $l=a^{\prime}b^{\prime}g$ ．以上より $\begin{matrix} a b = (a^{'} g) (b^{'} g) = (a^{'} b^{'} g) g = l g \end{matrix}$ が成り立つ．

定理 6.

整数 $a, b$ が互いに素でかつ $a c$ が $b$ で割り切れるとき， $c$ は $b$ で割り切れる．

$a, b$ が互いに素であることより， $a b$ は $a, b$ の最小公倍数．また， $a c$ は $b$ で割り切れるから， $a, b$ の公倍数．したがって， $a c$ は $a b$ の倍数．ゆえに， $c$ は $b$ で割り切れる．

定義 3 (素数).

$1$ より大きい整数 $p$ が $1$ と $p$ 以外に約数を持たないとき， $p$ を素数とよぶ．

定理 7.

$p$ を素数とする．整数 $a$ が $p$ で割り切れないならば， $a, p$ は互いに素である．

対偶を示す． $a, p$ が互いに素でないとすると， $a, p$ は $1$ より大きい公約数 $d$ をもつ． $p$ は素数だからその約数は $1$ または $p$ なので， $p=d$ ．よって $a$ は $p$ で割り切れる．

定理 8 (数の元素).

$a, b$ を整数， $p$ を素数とする． $a b$ が $p$ で割り切れるならば， $a$ が $p$ で割り切れるか， $b$ が $p$ で割り切れる．

$a b$ が $p$ で割り切れるとする． $a$ が $p$ が割り切れるならば，主張は正しい． $a$ が $p$ で割り切れないとき，前命題より， $a$ と $p$ は互いに素である． $a b$ が $p$ で割り切れるので，定理 6より $b$ が $p$ で割り切れる．

定理 9.

$n$ を正の整数とする． $n$ 個の整数の積が素数 $p$ で割り切れるとき，そのどれかは $p$ で割り切れる．

$n$ についての帰納法． $1$ 個の整数の積が $p$ で割り切れれば，その $1$ つの整数が $p$ で割り切れている． $n$ 個未満の整数の積が $p$ で割り切れると，そのどれかが $p$ で割り切れるとする． $n$ 個の整数 $a_{1},a_{2},\ldots,a_{n}$ に対して $a_{1}a_{2}\cdots a_{n}$ が $p$ で割り切れるとする． $a_{1}$ が $p$ で割り切れるならば主張は正しい． $a_{1}$ が $p$ で割り切れないとき，前命題より $a_{2}\cdots a_{n}$ は $p$ で割り切れる．帰納法の仮定より $a_{2},\ldots,a_{n}$ のどれかは $p$ で割り切れる．

定理 10 (素因数分解の可能性).

$1$ より大きい任意の正の整数 $n$ は，素数の積である．ここで，素数そのものも素数の積とみなす．

$n$ についての帰納法． $n=2$ のとき， $2$ は素数なので主張は正しい． $n>2$ として， $1$ より大きく $n$ より小さな整数が素数の積であると仮定する． $n$ が素数のとき主張は正しい． $n$ が素数でないとき， $1$ より大きく $n$ より小さい正の整数 $a, b$ が存在して $n=ab$ と表せる．帰納法の仮定より， $a, b$ は素数の積だから $n$ も素数の積である．

定理 11 (素因数の存在).

$1$ より大きい整数 $n$ に対して，ある素数 $p$ と整数 $m$ が存在して $\begin{matrix} n = p m \end{matrix}$ と表せる．

前命題より $n$ は素数の積で表せるので，主張は正しい．

定義 4 (素因数リスト).

$1$ より大きい正の整数 $n$ に対して， $\begin{matrix} n = p_{1} p_{2} \dots p_{r}, p_{1} ≦ p_{2} ≦ \dots ≦ p_{r} \end{matrix}$ を満たす素数の列 $(p_{1},p_{2},\ldots,p_{r})\in\mathbf{Z}^{r}$ を， $n$ の素因数リストと呼ぶ．素因数分解の可能性より，素因数リストは少なくとも1つ存在する

定理 12 (素数の素因数リスト).

素数 $p$ に対して， $p$ の素因数リストは $(p)$ であり，一意的である．

$(p_{1},p_{2},\ldots,p_{n})$ が $p$ の素因数リストだとすると $\begin{matrix} p = p_{1} p_{2} \dots p_{n} \end{matrix}$ と表せる．各 $p_{i}$ は $p$ の約数なので， $1$ か $p$ である．しかし， $p_{i}$ は素数なので $p_{i}=p$ ．すなわち $p=p^{n}$ ．よって $n=1$ となり， $p$ の素因数リストは $(p)$ しかありえない．

定理 13 (素因数分解の一意性).

$n$ を $1$ より大きい整数とする． $n$ の素因数リストは一意的である．すなわち，2つの列 $\begin{matrix} (p_{1}, p_{2}, \dots, p_{r}), (q_{1}, q_{2}, \dots, q_{s}) \end{matrix}$ が共に $n$ の素因数リストのとき，これらは等しい．つまり， $r=s$ かつ任意の $1\leqq i\leqq r$ に対して $p_{i}=q_{i}$ が成り立つ．

$n=2$ のときは前命題より素因数リストは $(2)$ しかない． $n>2$ として， $1$ より大きく $n$ より小さい整数の素因数リストが一意的だと仮定する． $n$ が素数の場合は，前命題より $(n)$ が唯一つの素因数リストになる． $n$ が素数でないとき， $p$ を $n$ の最小の素因数とすると， $n=pm$ を満たす $1$ より大きく $n$ より小さな正の整数 $m$ が存在する． $n$ の素因数リスト $\begin{matrix} (p_{1}, p_{2}, \dots, p_{r}) \end{matrix}$ を任意にとると， $\begin{matrix} n = p_{1} p_{2} \dots p_{r} (p_{1} ≦ p_{2} ≦ \dots ≦ p_{r}) \end{matrix}$ と表せて， $p$ は素数だから定理 8より， $p$ は $p_{1},p_{2},\ldots,p_{r}$ のいずれかを割り切り， $p$ が最小の素因数であることより， $\begin{matrix} p_{1} = p, p_{2} \dots p_{r} = m \end{matrix}$ である．よって， $n$ の素因数リストを任意にとると，必ず最初の素数は $p$ になる．次に $\begin{matrix} (q_{1}, q_{2}, \dots, q_{s}) \end{matrix}$ を $n$ の素因数リストとすると， $q_{1}=p$ かつ $\begin{matrix} (p_{2}, p_{3}, \dots, p_{r}), (q_{2}, q_{3}, \dots, q_{s}) \end{matrix}$ は $m$ の素因数リストだから，帰納法の仮定よりこれらは等しい．以上より $n$ の $2$ つの素因数リストは等しい．