10 |
背理法の証明例 |
有名な「素数は無限個存在する」という定理の証明を背理法で行います。
- 「素数が有限個である」と仮定する。
- $P$を、有限個の中で最大の素数$\dagger 1$とする。
- $Q=P\ !+1$という数$Q$を考える。
- $Q$が素数である場合は、明らかに$Q\gt P$であり、2.に反するので、$Q$は合成数$\dagger 2$。
- $Q$が合成数である場合は、定義より$Q$を割り切る素数$R$が存在し、また$Q=P\ !+1$であることから、$Q$は$P$以下の全ての素数で割り切れないため、$R\gt P$であることになり、同じく2.に反す。
- 2.を仮定すると、必ず矛盾が起きるため2.は成立しない。よって、素数は無限個数あることが証明された。
$\dagger 1$: 素数の定義:自然数$X$が$X$自身と$1$で割り切れ(自明)、かつそれら以外の全ての自然数で割り切れない$X$を素数と呼ぶ。
$\dagger 2$: 合成数の定義:自然数$Y$が$Y$自身と$1$で割り切れ(自明)、かつそれら以外の$Y$を割り切る素数が存在するとき、$Y$を合成数と呼ぶ。
Leave a Comment