2022/1/20 整数
素因数分解の存在と一意性の証明を紹介します.
⇨予備知識
・ →整数の除法の原理
・ →約数,倍数,最大公約数,最小公倍数
素因数分解とは,$1$ より大きい整数を素数の積に分解することを言います.たとえば, $6$ を素因数分解すると,$6=2\times 3$,$12$ を素因数分解すると,$12=2\times 2\times 3=2^2\times 3$,$3628800$ を素因数分解すると $3628800=2^8\times 3^4\times 5^2 \times 7$ などのようになります.すべての整数が素数の積に分解できることや,その分解の仕方が素因数の順序を無視するとただ一通りに定まることは,直感的には当たり前のような気がしますが,きちんと数学的に証明することができます.この事実は算術の基本定理などと呼ばれることもあります.
素因数分解の存在と一意性 (算術の基本定理): $1$ より大きい整数は素数の積に分解される.さらに,素因数の順序を無視すると,その分解の仕方はただ一通りである.
以下では,上の定理の証明を与えます.素因数分解が存在すること(存在性)と,その分解の仕方がただ一通りに決まる(一意性)をそれぞれ分けて示します.
$1$ より大きいどのような整数も素数の積に分解できることを示します.
素因数分解の存在の証明: $N$ を $1$ より大きい整数とする.$N$ が素数の積に分解されることを示す. $N$ が素数ならば,明らかに定理は成り立つ.そこで,$N$ を合成数とする.このとき,$N$ は少なくとも一つの素因数をもつので, $$N= p_1 \times N_1~~ (N> N_1 >0)$$ とかける.$N_1$ が素数ならば定理は成り立つ.$N_1$ が合成数ならば,$N_1$ は少なくとも一つの素因数をもつので, $$N= p_1 \times p_2 \times N_2 ~~ (N> N_1 >N_2 >0)$$ とかける.($p_1=p_2$ であってもよい.) 以下,同様に繰り返すと,整数 $N_i~(i\ge 1)$ は合成数である限り真に減少していくので,いずれ素数となる.つまり, $$N=p_1 \times p_2 \times \cdots \times p_{k-1}\times N_k ~~ (N_k \text{は素数})$$ とかける.$p_k = N_k$ とおくと, $$N=p_1 \times p_2 \times \cdots \times p_{k-1}\times p_k$$ となり,$N$ は素数の積に分解される.
素因数分解の一意性を示すための準備として,以下のユークリッドの補題と呼ばれる命題を示します.整数問題でよく使われる基本的な命題です.
ユークリッドの補題: $a, b$ を整数,$p$ を素数とする.このとき,次が成り立つ.
$p$ は $ab$ の約数 $\Rightarrow$ $p$ は $a$ の約数または $b$ の約数
ユークリッドの補題の証明: $p$ は $ab$ の約数という仮定のもとで,『$p$ が $b$ の約数でない $\Rightarrow$ $p$ は $a$ の約数』を示せばよい. $p$ は $b$ の約数でないので,$p$ と $b$ の最大公約数は $1$ である. ここで,$2$ つの正の整数の積はその最大公約数と最小公倍数の積に等しいので,($p$ と $b$ の最大公約数) $\times$ ($p$ と $b$ の最小公倍数) $=$ $pb$ である. よって,($p$ と $b$ の最小公倍数) $=$ $pb$ となる.一方,仮定より,$p$ は $ab$ の約数で,$b$ は $ab$ の約数なので,$ab$ は $p$ と $b$ の公倍数となる.最小公倍数は公倍数の約数なので,$pb$ は $ab$ の約数となる.したがって,$p$ は $a$ の約数である.
ユークリッドの補題を繰り返し用いると,次のようにユークリッドの補題を一般化することができます.
ユークリッドの補題の一般化: $a_1,\ldots,a_n$ を整数,$p$ を素数とする.このとき,次が成り立つ.
$p$ は $a_1\times a_2\times \cdots \times a_n$ の約数 $\Rightarrow$ ある整数 $i~(1\le i \le n)$ が存在して,$p$ は $a_i$ の約数
さて,ユークリッドの補題を用いて,素因数分解の仕方が素因数の順序を無視するとただ一通りに定まることを示しましょう.
素因数分解の一意性の証明:$N$ を $1$ より大きい整数とする.$N$ の素数の積への分解の仕方がただ一通りであることを示す. $N$ がつぎのように $2$ 通りの方法で素数の積に分解されたとする.ただし,$n\le m$ とする. $$N=p_1 \times p_2 \times \cdots \times p_{n-1}\times p_n$$ $$N=q_1 \times q_2 \times \cdots \times q_{m-1}\times q_m$$ このとき,$q_1$ は $p_1 \times p_2 \times \cdots \times p_{n-1}\times p_n$ の約数なので,ユークリッドの補題の一般化より,$q_1$ はある整数 $i~(1\le i \le n)$ が存在して,$p_i$ の約数である.必要なら添字を付け替えることで,一般性を失うことなく $p_i=p_1$ としてよい.一方,$p_1$ も素数なので,$p_1$ は $q_1$ の約数である.したがって,$p_1=q_1$ となる. すると, $$p_2 \times \cdots \times p_{n-1}\times p_n=q_2 \times \cdots \times q_{m-1}\times q_m$$ が成り立つ.以下,同様にして(必要なら添字を付け替えることで),$p_2=q_2,…,p_n=q_n$ が得られ,$n=m$ であることが示される.(もし,$n< m $ とすると,$1=q_{n+1}\times \cdots \times q_m > 1$ となり矛盾) したがって,素数の積への分解の仕方は順序を無視するとただ一通りに定まる.