Posts Issued on January 10, 2023

背理法の証明例

posted by sakurai on January 10, 2023 #579

有名な「素数は無限個存在する」という定理の証明を背理法で行います。

  1. 「素数が有限個である」と仮定する。
  2. $P$を、有限個の中で最大の素数$\dagger 1$とする。
  3. $Q=P\ !+1$という数$Q$を考える。
  4. $Q$が素数である場合は、明らかに$Q\gt P$であり、2.に反するので、$Q$は合成数$\dagger 2$。
  5. $Q$が合成数である場合は、定義より$Q$を割り切る素数$R$が存在し、また$Q=P\ !+1$であることから、$Q$は$P$以下の全ての素数で割り切れないため、$R\gt P$であることになり、同じく2.に反す。
  6. 2.を仮定すると、必ず矛盾が起きるため2.は成立しない。よって、素数は無限個数あることが証明された。

$\dagger 1$: 素数の定義:自然数$X$が$X$自身と$1$で割り切れ(自明)、かつそれら以外の全ての自然数で割り切れない$X$を素数と呼ぶ。
$\dagger 2$: 合成数の定義:自然数$Y$が$Y$自身と$1$で割り切れ(自明)、かつそれら以外の$Y$を割り切る素数が存在するとき、$Y$を合成数と呼ぶ。


左矢前のブログ 次のブログ右矢