公約数、素数、そしてバーゼル問題

Jul 17, 2012

2人が同時に好きな自然数を叫びます。
A：「10」
B：「132」
この2つの数字はどちらも2で割り切れます。難しい言葉で言うと「この2つの数字の公約数は2」ということです（小学校で習うんだったかな）。

ではもう一度
A：「65」
B：「154」
この2つの場合はどうでしょう。すぐに分かりますがこの2つの数字には公約数はありません。難しい言葉でいうと「この2つの数字は互いに素」ということです。

ではここで問題「任意に2つの数字が互いに素である確率は？」

ちょっと実験してみようにもこれはなかなか難しいです。
というのも、任意の自然数ですから、10とか250とかはもちろん
20482093840734198720491209341412987461298402971029347019823740194
や
93410974246817469817648164815451276453725653666635467341618253600027
みたいのでもいいですし、、、というか、こういう数字も公平に出てこないと実験になりません。

さあ数字を言え！といってこんな数字を挙げられる人はいないでしょう。じゃあコンピューターで、といっても無限にある自然数をすべて公平に挙げるのは無理でしょう。

しかし人間の知性に限界はありません。この問題を理論的に解きましょう。

例えば、8と16の公約数は2、4、8となりますが、互いに素かどうかを見るには素数の公約数だけみればいいということに注目します。この例なら4で割れるかどうかを調べはしません。素数2で割れるかを見るだけです。
15と105なら素数3で割れます。 8と105なら素数2、素数3、素数5、素数7…と素数を順に調べてどの素数も共通の公約数になっていない、つまり互いに素だと分かります。

任意の自然数 $N$ が素数 $p$ で割れる確率は、 ${1}/{p}$ であるというのは分かりますか？
例えば、素数3で割れる数というのは $3\;,6,\;9,\;12,\;\cdots$ となります。つまり全自然数の3つに1つが素数3で割れる自然数だということになります。パッと選んだ自然数が3で割れるかは3つに1つ、つまり確率1/3となります。