151004(3)

Ruby

素数が無数に存在すること(1)

素数が無数に存在することの証明はたくさんあるが、ユークリッドの証明を真似て次のように示してみた。

p0, p1を異なる素数とする。

m1 = p1 + p0 とおく。

①m1 が素数なら、p0, p1 と異なる素数である。

②m1 が合成数なら、p0, p1 で割り切れないので、m1 はp0, p1 と異なる素因数を含む。

①の場合、p2 = m1 とし、②の場合、p0, p1 と異なるm1 の素因数のうち最小のものをp2 とする。

m2 = p1 * p2 + p0 とおく。

①m2 が素数なら、p0, p1, p2 と異なる素数である。

②m2 が合成数なら、p0, p1, p2 で割り切れないので、m2 はp0, p1, p2 と異なる素因数を含む。

①の場合、p3 = m2 とし、②の場合、p0, p1, p2 と異なるm2 の素因数のうち最小のものをp3 とする。

m3 = p1 * p2 * p3 + p0 とおく。

先程と同様にして、p0, p1, p2, p3 と異なる素数p4 が見つかる。

このことを繰り返せば、任意の自然数Nに対し、異なるN個の素数が見つかる。

よって、素数は無数に存在する。

ユークリッドの証明および上記の証明で行なっている作業を以下のように書いてみた。

require 'prime'

# 素因数の候補
p_ary = Prime.each(10 ** 8).to_a

ans =
[[2, 1, 16],
 [3, 1, 16], [3, 2, 21],
 [5, 1, 18], [5, 2, 14], [5, 3, 17],
 [7, 1, 16], [7, 2, 12], [7, 3, 19], [7, 5, 20]]

ans.each{|a, b, n|
  ary = [a]
  s = a
  i = 1
  while i < n
    s0 = s + b
    if s0.prime?
      a = s0
    else
      j = 0
      # aryに含まれていないs0の素因数を探す
      while ary.include?(p_ary[j]) || s0 % p_ary[j] > 0
        j += 1
      end
      a = p_ary[j]
    end
    ary << a
    s *= a
    i += 1
  end
  p ary
}

出力結果
[2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[3, 2, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[3, 5, 17, 257, 65537, 641, 7, 318811, 19, 1747, 12791, 73, 90679, 67, 59, 113, 13, 41, 47, 151, 131]
[5, 2, 11, 3, 331, 19, 199, 53, 21888927391, 29833, 101, 71, 23, 311, 7, 72353, 13, 227]
[5, 7, 37, 1297, 17, 3, 13, 11, 953, 19, 24239, 5376221562149172737, 36061, 2633]
[5, 2, 13, 7, 11, 17, 167, 4079, 487, 73, 421, 2382557, 337, 19, 577, 29573, 97]
[7, 2, 3, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[7, 3, 23, 5, 2417, 1021, 19, 79, 17, 66643, 13, 11]
[7, 2, 17, 241, 19, 5, 29, 23, 52673, 113, 5101, 127, 31, 1013, 97, 17327749, 83, 73859, 43]
[7, 2, 19, 271, 72091, 29, 3, 452117408867, 6959, 55691, 23, 659, 11141863, 11, 171881, 677, 31181, 313, 819493, 4871]