互いに素の意味と関連する三つの定理
互いに素とは,2つの整数の最大公約数が1であることを言う。例えば, と の最大公約数は なので, と は互いに素。
「互いに素」の意味と,関連する定理を解説します。定理1,2は基本的な内容ですが,定理3は数学マニア向け(美しい!)です。
互いに素とは
連続する整数は互いに素
合同式の割り算
互いに素になる確率
互いに素とは
互いに素とは,
「2つの整数の最大公約数が 」
または
「2つの整数が,ともに同じ2以上の整数で割り切れることは無い」
という状況を表します。
例えば, と の最大公約数は なので, と は互いに素です。
一方, と の最大公約数は なので, と は互いに素ではありません。
連続する整数は互いに素
連続する二つの整数: と ,は互いに素である。
背理法で証明する。 と が互いに素でないと仮定する。このとき, と の両方を割り切る整数 が存在する。
の倍数どうしの差も の倍数なので, も の倍数となる。これは に矛盾。
このように,互いに素であることを証明するときには,背理法を使うとうまくいくことが多いです。
また「連続する整数は互いに素」という性質は,整数問題でときどき活躍するので覚えておきましょう。
合同式の割り算
続いて合同式の重要な性質についてです。合同式の両辺を同じ整数 で割ってよいのは, と法 が互いに素なときだけです。→合同式の意味とよく使う6つの性質
で と が互いに素なら
が の倍数
が の倍数
の素因数分解を とする。
- は素因数 を 個以上持つ
- は と互いに素なので は素因数 を一つも持たない
以上より が素因数 を 個以上持つ
同様に に対しても, が素因数 を 個以上持つことが分かる。よって, が の倍数,つまり となる。
注: と法 が互いに素でないときは合同式の両辺を で割ってはいけません。例えば ですが,両辺を で割った式 は間違いです。
互いに素になる確率
以上 以下の数を二つランダムに選ぶ(→注)とき,その二つの数が互いに素になる確率を とおく。このとき
注:同じ整数を二つ選ぶのもOKです。(選ぶ順番も考慮すると)全部で 通りの場合があり,それぞれ確率 で起こります。
一部厳密ではありませんが,考え方はかなり面白いです。
二つの整数 と が互いに素
→
と
のどちらかは
の倍数でない,かつ
と
のどちらかは
の倍数でない,かつ
と
のどちらかは
の倍数でない,かつ
ここで, が十分大きいとき と のどちらかは素数 の倍数でない確率は
よって, が大きいとき求める確率は(→注)
逆数を取って変形していく:
ただし,等号の理由はそれぞれ
三つ目:無限等比級数の公式
四つ目:展開して項を比較
最後:バーゼル問題
注: や が「 の倍数である」という事象,「 の倍数である」という事象,「 の倍数である」という事象, が互いに独立であることを使いました。
「互いに素」は「最大公約数が 」と同じことですが,「最大公約数が 」と書くよりも「互いに素」と書く方が少し楽です。