2.1.5 素因数分解の一意性

いよいよ素因数分解の一意性を証明します。経験上明らかな素因数分解もきちんと証明するには、最大公約数の定義→ユークリッドの互除法→最大公約数の生成定理→ユークリッドの補題といくつかの経過をたどる必要があります。また、このような経過をたどることにより、将来、整数の範囲を拡張し素因数分解の一意性を証明する際に生きてきます。

補題 2.1.29 (ユークリッドの補題)
素数$p$が整数 $nm (n,mは整数)$の約数であるとき、$p$は、$n$又は$m$の約数である。 つまり、

$$p\mid nm \Longrightarrow p\mid n 又は p\mid m$$

素因数分解が一意的であることを前提とすれば、この定理はその特殊な場合です。しかし、素因数分解の一意性はこの時点では証明できていません。ここでは定理2.1.17を用いて証明します。つまり、ユークリッドの補題は素因数分解の一意性よりも基本的なものだといえます。

証明

仮に$p$が$n$の約数でないとすると、$p$が素数であることを考えると$p,n$は1以外の公約数を持たないため互いに素です。したがって、$ap+bn=1$となる整数$a,b$が存在します。 同様に、$p$が$m$の約数でもないとすると、$a'p+b'm=1$となる整数$a',b'$が存在します。

これらの式をかけ算することにより、 $(ap+bn)(a'p+b'm)=1$となります。左辺を展開し、 $p,nm$でまとめると、 $(aa'p+ba'n+ab'm)p+bb'nm=1$となります。したがって、定理2.1.17より、$p,nm$は互いに素となりますが、これは、$p$が$nm$の約数であるとの仮定に反します。従って、$p$が$nm$の約数であれば、$p$は、$n,m$のいずれかの約数になります。

本講のメインテーマである素因数分解の一意性を示しましょう。$n$を自然数とすると、$n$は素因数分解でき、その方法は1通りであることは経験的に知っていると思います。このことを厳密に証明しましょう。

定義 2.1.30
素因数分解が一意的（unique-prime-factorization）であるとは、自然数$n$が2通りの素因数分解

$$n = p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k} (p_1<p_2<\cdots<p_kは素数、n_1,n_2,\cdots,n_kは自然数)$$

$$= q_1^{m_1}q_2^{m_2}\cdots q_l^{m_l} (q_1<q_2<\cdots<q_lは素数、m_1,m_2,\cdots,m_lは自然数)$$

ができた場合、$k=l$であり、 $p_1=q_1,p_2=q_2,\cdots,p_k=q_k$（ここで、$k=l$であることに注意)、 $n_1=m_1,n_2=m_2,\cdots,n_k=q_k$となることを意味します。

つまり、「素数の積として、積の順番の違いを除いてただ一通りに表すことができる」ことを意味します。

定理 2.1.31 (素因数分解の一意性、算術の基本定理)
2以上の自然数は素因数分解できその方法は一意的である。

証明
数学的帰納法で示します。

$n$を2以上の自然数とする。$n=2$のとき、2は素数であるため素因数分解可能でありその方法は一意的です。そこで、$n$以下の自然数（ただし2以上)は全て素因数分解可能であり、その分解は一意的であると仮定します。 $n+1$が素数の場合、それ自身が素因数分解可能です。$n+1$が素数でない場合、$1とn+1$以外に約数があるため、その約数を $n_1とすると、n+1=n_1\times n_2$と分解でき、 $n+1>n_1,n_2$です。このとき、帰納法の仮定から、$n_1,n_2$が素因数分解できますので、$n+1$も素因数分解できます。以上より、2以上の自然数が素因数分解可能であることが示されました。

ついで、素因数分解の一意性を示します。ここで、これまでの知識を使います。 $n+1$が2つの方法で素因数分解できるたとする。つまり

$$n+1 = p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k} (p_1<p_2<\cdots<p_kは素数、n_1,n_2,\cdots,n_kは自然数)$$

$$= q_1^{m_1}q_2^{m_2}\cdots q_l^{m_l} (q_1<q_2<\cdots<q_lは素数、m_1,m_2,\cdots,m_lは自然数)$$

ここで、$p_1=q_1$であれば、 $n+1をp_1(=q_1)$で割ったものは$n$以下であるため、帰納法の仮定を適用することにより、一意性は証明できます。仮に、$p_1<q_1$とすると、次に示す補題より、 $p_1はq_1,\cdots,q_l$のいずれかを割り切るが、 $q_1,\cdots,q_l$はいずれも素数であり、 $p_1<q_1,\cdots,q_l$であることを考えるとこれは成立しない。よって証明できた。