整数\(a\)を素因数分解したいとき,\(a\)を割り切る素数を探すだろう.そのような場合,\(\sqrt{a}\)以下の素数で割り切れるかどうかだけ確かめれば良い.つまり,次が成り立つ.

整数\(a\)が\(\sqrt{a}\)以下の素数で割り切れなければ,素数である.

503は素数だろうか.\(22< \sqrt{503} < 23\)だから,22以下の素数,2,3,5,7,11,13,17,19で割り切れるか調べれば良い.
割り切れないから,503は素数である.

 この主張を証明しよう.

proof
素数でないとすると,\(a\)は$2$以上の整数$p,q$を用いて\(a=pq\)とかける.\(p\)としては\(a\)で割り切れる素数で最小の素数を持ってくる.
$p$は$a$で割り切れる最小の素数なので,$q$は必ず$p$以上である.また,仮定より$p$は$\sqrt{a}$より大きい.すると,\[a=pq\geq p^2 \gt (\sqrt{a})^2=a\]これは矛盾である.




コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です