二つの整数が素になる確率：整数の中から任意に選んだ2つの数が互いに素である確率から円周率πを求める

2021年6月6日 17:46

整数の中から任意に2つの数を選んだとき互いに素である確率

　整数の中から任意に2つの数を選ぶ。このとき、その二つの数が互いに素である(共通の約数を持たない)確率は

に等しい。これを確かめてみる。

いくつかの問題

　確かめるに当たって、いくつかの問題がある。まず、そもそも任意に２つの整数を選ぶことが本当に出来るのか、ということだ。
　いや、「無限集合の中からランダムに取り出すことが出来るのか」というような選択公理が正しいのか？という難しい話ではない。まあ、取り出せたとしよう。すると、まあ殆どの場合、殆ど無限に近いような巨大な数であるはずだ(絶対値が)。取り出した整数が10000桁程度の小さな数である確率は無限小と言って良い。こんな大きな数の素因数分解など出来やしない。
　その他にもいくつかの問題があるが、実際に計算して確かめるために、以下のように決める。

　(1) 選択する数は計算できるような小さな数から選ぶ(10000以下とか)
　(2) 負の整数は除く。これは計算を楽にするため。確率の計算結果は変わらないはずだ。
　(3) 0と1も除く。

　(3)について補足すると、0は全ての数の倍数であり、1は全ての数の約数であるというかなり特別な数だ。全ての非負の整数から任意の2つの数を選択する場合、0,1が選択される可能性はほぼ0であるが、計算できるような小さな数から選択すると、この2つの特別な数が選ばれる確率が不当に高くなってしまう。従って0,1を除くことにした。0,1が選ばれる可能性がほぼ0であることから、除いても元確率の計算結果は変わらないはずだ。

実際の計算

　まあ、パソコンでやるのが良いだろう。例えば10000以下の整数から2つの数をランダムに選び、それぞれを素因数分解して…と考えていたが、10000以下程度なら、ランダムに選ぶよりも、全ての組み合わせを計算してしまった方が良いだろう。また、互いに素かどうかは、それぞれを素因数分解するよりも、ユークリッドの互除法を用いて公約数が1かどうかを確認した方が速い。
　ユークリッドの互除法はこんな感じ。

Function Kouyakusu(x：整数, y：整数)：整数
If x Mod y = 0 Then
Kouyakusu ← y
Exit Function
End If
Kouyakusu ← Kouyakusu(y, x Mod y)
End Function

　これを2つの整数をx,yに入れて呼び出せば良い(プログラミング言語によっては、x≧yにする必要があるかも知れない)。公約数が1の場合が互いに素だ。

計算結果

　計算結果は以下のようであった。

　範囲　組み合わせ総数　互いに素であった数　その確率　得られたπの値
　2～9　　　　64　　　　　　　38　　　　　　0.59375　　3.178877657
　2～99　　　9604　　　　　　5810　　　　0.604956268　3.14929711
　2～999　　996004　　　　　605586　　　0.608015630　3.141363933
　2～9999　99960004　　　　60766974　　0.607912881　　3.141629399

　一応説明すると、例えば2～9の場合、2つの数を選ぶ組み合わせは2～9の8通り×8通りで全部で64通り、その組み合わせのうち互いに素であったのは38通り、38/64=0.59375、その値を6/(πの2乗)として得られた値(逆数を取って6を掛けて平方根を計算)が3.178877657、という意味だ。
　二桁の数だけで3.14…まで出るのは以外だった。

証明(のようなもの)

　厳密ではないが、元の確率を一応証明しておく。

　ある数が素数pの倍数である確率は1/p
　2つの数が両方ともpの倍数である確率は(1/p)×(1/p)
　従って、少なくともどちらか一方がpの倍数でない確率は