📂整数論

素数分解の定理

定理 ¹

素数 $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}$ のいずれかを割らなければならないことになる。

■