WOO logo

Wizard のオススメ

最大素数は存在しないことの証明

今週も数学の証明への旅を続けます。今日はよくある証明、つまり最大の素数は存在しないという証明を取り上げます。いつものように、できるだけ簡単な英語で説明し、難しい数学的表記は避けることを目標としています。しかし、その前に、いつもの論理パズルを出題します。

ロジックパズル

あなたは106階建てのビルにいます。各階は0階から105階まで番号が振られています（アメリカ以外の世界のほとんどの国では、階数に番号が振られています）。地面に置かれた大きな羽根の箱に卵を安全に落とせる最高階をテストしたいとします。屋上から落とした卵は割れますが、0階から落とした卵は割れないことが分かっています。実験には卵が2個あります。最悪のシナリオで、必要な最小の落下回数はいくつでしょうか？

答えと解決方法はコラムの最後に表示されます。

最大素数は存在しないことの証明

最大の素数は存在しないことを、背理法によって証明します。言い換えれば、その逆、つまり最大の素数が存在するという主張を反証します。

最大の素数を p n (つまり n 番目の素数) と呼び、すべての素数を次の順序でラベル付けしましょう。

p 1 = 2、p 2 = 3、p 3 = 5、p 4 = 7、…p n =?

次のような数値 N を考えます。

N = p 1 × p 2 × p 3 × p 4 × … × p n +1。

Nが素数の場合、それより小さい素数はそれを割り切れません。しかし、p nまでの任意の素数をNで割ると、余りは1になります。それは次の 2 つの方法でしか説明できません。

  1. N 自体は素数であり、 p nより大きくなければなりません。
  2. p nよりも大きく、N を均等に割り切れる素数が存在します。

いずれにしても、 p nよりも大きな素数が存在することが示されました。

例えば、小さな素数を見てみましょう。31が最大の素数だと仮定するとどうなるか見てみましょう。この場合：

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1,805,044,411,171

素因数計算機を使うと、1,805,044,411,171 = 1,061,729 × 1,700,099 となります。つまり、31 より大きい素数が 2 つ見つかりました。1,061,729 と 1,700,099 です。

別の例を挙げると、7が最大の素数だと仮定します。すると、N = 2×3×5×7 + 1 = 211となります。211を素因数分解すると、211は素数であることがわかります。つまり、7よりも大きな素数を見つけたことになります。

どの素数が最大であると仮定しても、この方法ではそれよりも大きな素数が見つかります。

論理パズルの答え

14

14 ドロップ以内で最高の安全フロアを見つける方法は次のとおりです。

  1. 最初の卵を14階から落とします。もし割れたら、1階から13階までを1つずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で1回、2番目の卵で13回）。割れた場合は、手順2に進みます。
  2. 13階まで登り、最初の卵を27階から落とします。もし卵が割れたら、15階から26階までを1階ずつテストします。割れた場合に必要な最大落下数は14（最初の卵で2個、2つ目の卵で最大12個）。割れた場合は、手順3に進みます。
  3. 12階まで登り、最初の卵を39階から落とします。もし卵が割れたら、28階から38階までを1階ずつテストします。割れた場合に必要な最大落下数は14（最初の卵で3、2つ目の卵で最大11）。割れた場合は、手順4に進みます。
  4. 11階まで登り、最初の卵を50階から落とします。もし卵が割れたら、40階から49階までを1階ずつテストします。割れた場合に必要な最大落下数は14（最初の卵で4、2つ目の卵で最大10）。割れた場合は、ステップ5に進みます。
  5. 10階まで登り、最初の卵を60階から落とします。もし割れたら、51階から59階までを1階ずつテストします。卵が割れた場合に必要な最大ドロップ数 = 14（最初の卵で5、2番目の卵で最大9）。それ以外の場合は、手順6に進みます。
  6. 9階まで登り、最初の卵を69階から落とします。もし卵が割れたら、61階から68階までを1階ずつテストします。割れた場合に必要な最大落下数は14（最初の卵で6個、2つ目の卵で最大8個）。割れた場合は、手順7に進みます。
  7. 8階まで登り、77階から最初の卵を落とします。もし卵が割れたら、70階から76階までを1階ずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で7個、2つ目の卵で最大7個）。割れた場合は、手順8に進みます。
  8. 7階まで登り、84階で最初の卵を落とします。もし卵が割れたら、78階から83階までを1階ずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で8個、2つ目の卵で最大6個）。割れた場合は、手順9に進みます。
  9. 6階まで登り、最初の卵を90階から落とします。もし卵が割れたら、85階から89階までを1階ずつテストします。割れた場合に必要な最大落下数は14（最初の卵で9個、2つ目の卵で最大5個）。割れた場合は、ステップ10に進みます。
  10. 5階まで登り、95階から最初の卵を落とします。もし卵が割れたら、91階から94階までを1階ずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で10個、2つ目の卵で最大4個）。割れた場合は、ステップ11に進みます。
  11. 4階まで登り、最初の卵を99階から落とします。もし卵が割れたら、96階から98階までを1階ずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で11個、2つ目の卵で最大3個）。割れた場合は、ステップ12に進みます。
  12. 3階まで上がり、102階から最初の卵を落とします。もし卵が割れたら、100階と101階を1階ずつテストします。割れた場合に必要な最大落下数は14です（最初の卵で12個、2つ目の卵で最大2個）。割れた場合は、手順13に進みます。
  13. 2階上がり、104階から最初の卵を落とします。もし割れたら、103階でテストします。割れた場合に必要な最大ドロップ数は14です（最初の卵で13、2番目の卵で1）。割れない場合は、ステップ14に進みます。
  14. 1階上がって、105階から最初の卵を落とします。卵が割れた場合、安全な最高階は104階です。卵が生き残った場合、安全な最高階は105階です。

n階建ての建物の場合の一般的な戦略は、最初の落下を行うのに最適な階を見つけることです。最初のテストに合格したら、そこから同じ階数から1階引いた階数だけ上昇します。2回目のテストに合格したら、前回上昇した階数よりも1階少ない階数まで再び上昇します。これを繰り返し、前回のテスト間の上昇階数よりも1階少ない階数まで上昇します。最初の卵を使ったテストに不合格になった場合は、2つ目の卵を使って、最後の2つのテストの間にあるすべての階を、その範囲の最下階から順に系統的にテストします。

階数がn、n-1、n-2、…1と増加していくことに注目してください。これらの増加の合計はn(n+1)/2です。重要なのは、この数列の合計が建物の階数以上になるような、nの最小の整数値を見つけることです。

たとえば、500 階建てのビル (安全な 1 階は含まない) を考えてみましょう。次の式を解きます。

n(n+1)/2 = 500

n(n+1) = 1000

n 2 + n -1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">ピタゴラスの定理を使う:

n = (-1 +/- √4001 )/2 =~ 31.13

ただし、階数は整数値であるため、n = 32に切り上げます。したがって、500階（安全な1階を含めると501階）の場合、最初のテストは32階から行います。