📂整数論

算術の基本定理の証明

概要 ¹

natural number $n >2$ はユニークな素因数分解 $n = p_{1} p_{2} \cdots p_{r}$ を持つ。この時、素数 $p_{1} , p_{2} , \cdots , p_{r}$ の順序は無視される。

説明

小学校から自然に使ってきた性質が証明が必要だと聞いて驚くかもしれないが、非常に重要だ。これほど簡単であることそのものが、基本定理という名前を持つに値する証拠になるだろう。

証明

初等的証明

Part 1. 存在性

$2=2$ であり、$3= 3$ そして $4 = 2^2$ の時、ユニークな素因数分解が存在する。すべての可能な $n$ に対して素因数分解を見つけてみて、その最後の数が $N$ だとしよう。ここでは、$N+1$ が素数か合成数のどちらかなので、両方のケースをチェックしてみよう。

• Case 1. $N+1$ が素数の場合
  $N+1$ が素数である場合、それは自身が素因数分解されたことを意味する。
• Case 2. $N+1$ が合成数の場合
  $N+1$ が合成数であれば、二つの自然数の積 $N+1 = n_{1} n_{2}$ として表される。

$N$ までのすべての自然数に対して素因数分解を見つけることができたので、 $$n_{1} = p_{1} p_{2} \cdots p_{m} \\ n_{2} = q_{m+1} q_{m+2} \cdots q_{r}$$ それを単に掛け合わせることで、$N+1 = p_{1} p_{2} \cdots p_{r}$ となり、$N+1$ の素因数分解を求めることができる。したがって、$N+1$ に対して二つのケースすべてで素因数分解を見つけることができるので、$2$ より大きいすべての自然数は素因数分解を持つ。

---

Part 2. 一意性

次に、$n = p_{1} p_{2} \cdots p_{r}$ がユニークであることを示す必要がある。

$n$ の素因数分解がユニークではなく、$n = p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s}$ が成り立つと仮定する。これらの順序は一意性に影響を与えないので、便宜上、$p_{1} \le p_{2} \le \cdots \le p_{r}$ としよう。

素数分解の原理: 素数 $p$ が natural number $n : = d_{1} d_{2} \cdots d_{r}$ に対して $p \mid n$ の場合、$p$ は $d_{1} , d_{2} , \cdots , d_{r}$ の少なくとも一つを割らなければならない。

ある数を割る素数は、その約数の少なくとも一つを割らなければならないので、$p_{1}$ は $q_{1} , q_{2} , \cdots , q_{s}$ の中の一つを割る必要がある。順序は自由なので、$p_{1}$ で割り切れる $q_{i}$ を $q_{1}$ とし、$q_{1}$ を $q_{i}$ として扱っても構わない。

しかし、$q_{1}$ も $p_{1}$ と同じく素数であるので、$p_{1} = q_{1}$ が成り立ち $$p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s}$$ から両辺でそれを消去すると $$p_{2} \cdots p_{r} = q_{2} \cdots q_{s}$$ を得る。同じ方法で、一方が $1$ になるまで消去を続けることができる。この時、もう一方の辺が $1$ ではない場合、素数の積は必ず $1$ より大きくなり、等式が成り立たない。したがって、 $$p_{1} =q_{1} \\ p_{2} = q_{2} \\ \vdots \\ p_{i} = q_{i} \\ \vdots$$ が成り立ち、最終的に $p_{r} = q_{s}$ が成り立たなければならない。

■

代数的証明

算数の基本定理の代数的証明: 整数環 $\mathbb{Z}$](../587) は PIDであるため、UFDである。

■

コード

以下はRで素因数分解を実装したコードだ。素数かどうかを判断するプロセスがないため速い。素数リストを使うからだ。アルゴリズムとしてはほぼ無価値だ。素因数分解をリスト形式で返すため、可読性が落ちるかもしれない。指数形式に変換したい場合は、単に返されたベクトルに組み込み関数の table() を使えば良い。

prime = read.table("../attachment
                   /cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
 
factorize<-function(p)
{
  q=p
  factors<-numeric(0)
  i=1; j=1
  while(q!=1)
  {
    if(q%%prime[i]) {i=i+1}
    else
    {
      q<-q/prime[i]
      factors[j]<-prime[i]
      i=1
      j=j+1
    }
  }
  return(factors)
}
 
factorize(54)
factorize(101)
factorize(256)
factorize(420)
table(factorize(420))

以下はコードを実行した結果だ。