4月19日の中学生クラスのテーマは、先週に続いて整数論でした。今回は素数について調べました。
はじめに、エラトステネスの篩を使って、100以下の素数を求め、25個あることがわかりました。
また、素数の出現するようすはかなり不規則であることもわかります。
たとえば、50代の素数は53と59の2つだけ、60代の素数も61と67の2つだけですが、70代の素数はなんと71、73、79の3つもあります。
このように不規則な素数ですが、大局的に見ると出現頻度はだんだん減っていく傾向にあることがわかります。
こうして素数がどんどん希薄になっていくようすを目の当たりにすると、どんどん先まで進むにつれて、やがては素数がまったく現れなくなってしまうのではないかと思ってしまいます。古代人もそのように感じたことは確かです。というのは、紀元前500年ごろにギリシャで『原論』という数学の書物を編纂したユークリッドは、その本の中で「素数は無数にある」ことを証明しているからです。
ユークリッドは素数が無限個あることを背理法という方法を使って証明しているのですが、その証明は構成的でもあり、それによると n 個の素数が与えられたとき、いつでもその中にはない新しい素数を見つけ出すことができるのです。このアルゴリズムにしたがって構成される素数たちをユークリッドの素数といいます。
ところで、今年（2021年）の一橋大学の入試では、「1000以下の素数の個数は250個以下であることを示せ」という問題が出ました。
100までの素数が25個で、範囲を広げるにつれて素数は希薄になっていくことから、1000以下の素数が250個よりも少ないことは明らかなような気がします。
しかし、証明となると話は別です。上にも書いたように、素数の分布は不規則で、場所によっては「密に」存在するところもあるわけです。
1000までという範囲がそのような例外に当たっていないことを示すには、地道に計算するほかはないかもしれません。
しかし、そうだとしても、1000までの素数をエラトステネスの篩を使って求めていたのでは、解答時間も計算用紙も不足してしまうこともまた明らかです。
求められているのは、素数の個数が「250以下である」というかなりおおざっぱな評価に過ぎないのですから、何とか効率よく個数を「評価」する方法はないでしょうか。（ここで、「効率よく」と書いたのが、「試験時間内に」という意味であることはもちろんです。）
さて、この問題には、実はそのような「うまい」やり方があります。それは周期性に着目することです。
上で、素数の出現には規則性はないと書いたばかりなのに、何を言っているのかと思った読者もいるでしょう。
たしかに、素数の出現のしかたは相当に不規則です。
ですが、ここには確実に素数はないとわかる場所には周期的なものもあるのです。
たとえば、1の位が0か5である数は5以外にはすべて合成数です。なので、5を除外すれば、10, 15, 20, 25, …と等間隔に並ぶ数はすべて「合成数である」こと、したがって、そこには「素数は来ない」ことがわかるのです。こうして、素数が存在できる範囲を全体の約5分の4まで減らすことができます。あとは頑張って、この5分の4という割合を4分の1まで縮めていけばいいだけです。とは言っても、実際の計算はそうとうに厄介です。
このような、「手段を指定せずに評価せよとだけ問う問題」は、過去にもありました。
2003年の東大の入試で「円周率が3.05よりも大きいことを示せ」という問題が出たことがあったのです。
受験生は、このような「評価問題」は概して苦手だと想像されます。方法が指定されていないので、「当たりをつけて」いろいろやってみるほかはないからです。
それには、広い知識、発想力、構想力が必要です。
—–授業のようすはインスタグラムでも見ることができます。随時更新していますので、ご覧ください。