📂整数論

素数分解の原理

定理 ¹

素数 $p$ が自然数 $ n : = d_{1} d_{2} \cdots d_{r}$ に対して $p \mid n$ ならば、$p$ は $d_{1} , d_{2} , \cdots , d_{r}$ のうち少なくとも一つを割り切らなければならない。

説明

$p \mid n$ は $n$ が $p$ の倍数、すなわち $p$ が $n$ を割り切るということである。一見すると当たり前のように見えるが、これはれっきとした証明を要する素数だけの性質である。素数でなくても上の定理が常に成り立つかを考えてみよう。

証明

まず $n$ を二つの自然数の積、すなわち $n = ab$ とおき、$p$ が $a$ と $b$ の両方を割り切れないと仮定してみよう。

2元1次方程式に対する整数解の存在性: 二つの整数 $a,p$ に対して $ax + py = \gcd (a,p)$ は必ず整数解を持つ。

$p$ は $a$ を割り切らないので $a$ は $p$ の倍数ではなく、$p$ が素数であるため $\gcd (a,p) = 1$ である。したがって $$ ax + py = 1 $$ を満たす $(x,y)$ が存在する。ここで両辺に $b$ を掛けると $$ abx + pby = b $$ である。前提から $ab = n$ は $p$ の倍数であり、$pb$ はそもそも $p$ が掛けられているので見るまでもなく $p$ の倍数である。したがって $b$ は $p$ の倍数となるが、これは仮定に矛盾するので、$p$ は $a$ と $b$ のうち一方を割り切らなければならない。

再び $ n = d_{1} d_{2} \cdots d_{r}$ に戻ると、上の議論により $p$ は $d_{1}$ あるいは $(d_{2} \cdots d_{r})$ のうち一方を割り切らなければならない。

$d_{1}$ を割り切らなくても $d_{2} \cdots d_{r}$ に対して同じ議論を再び適用してみれば、結局 $p$ は $d_{1} , d_{2} , \cdots , d_{r}$ のうち一つを割り切らなければならないことになる。

■