1. 高校数学の美しい物語
  2. 互いに素の意味と関連する三つの定理

互いに素の意味と関連する三つの定理

更新日時 2021/03/07

互いに素とは,2つの整数の最大公約数が1であることを言う。例えば,3355 の最大公約数は 11 なので,3355 は互いに素。

「互いに素」の意味と,関連する定理を解説します。定理1,2は基本的な内容ですが,定理3は数学マニア向け(美しい!)です。

目次
  • 互いに素とは

  • 連続する整数は互いに素

  • 合同式の割り算

  • 互いに素になる確率

互いに素とは

互いに素とは,

「2つの整数の最大公約数が 11

または

「2つの整数が,ともに同じ2以上の整数で割り切れることは無い」

という状況を表します。

例えば,3355 の最大公約数は 11 なので,3355 は互いに素です。

一方,4466 の最大公約数は 22 なので,4466 は互いに素ではありません。

連続する整数は互いに素

定理1

連続する二つの整数:nnn+1n+1,は互いに素である。

証明

背理法で証明する。 nnn+1n+1 が互いに素でないと仮定する。このとき,nnn+1n+1 の両方を割り切る整数 p(2)p\:(\geq 2) が存在する。

pp の倍数どうしの差も pp の倍数なので,(n+1)n=1(n+1)-n=1pp の倍数となる。これは p2p\geq 2 に矛盾。

このように,互いに素であることを証明するときには,背理法を使うとうまくいくことが多いです。

また「連続する整数は互いに素」という性質は,整数問題でときどき活躍するので覚えておきましょう。

合同式の割り算

続いて合同式の重要な性質についてです。合同式の両辺を同じ整数 aa で割ってよいのは,aa と法 nn が互いに素なときだけです。→合同式の意味とよく使う6つの性質

定理2

abac(modn)ab\equiv ac\pmod{n}aann が互いに素なら

bc(modn)b\equiv c\pmod{n}

証明

abac(modn)ab\equiv ac\pmod{n}

    abac\iff ab-acnn の倍数

    a(bc)\iff a(b-c)nn の倍数

nn の素因数分解を p1e1p2e2pkekp_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} とする。

  • a(bc)a(b-c) は素因数 p1p_1e1e_1 個以上持つ
  • aann と互いに素なので aa は素因数 p1p_1 を一つも持たない

以上より (bc)(b-c) が素因数 p1p_1e1e_1 個以上持つ

同様に i=2,,ki=2,\cdots, k に対しても,(bc)(b-c) が素因数 pip_ieie_i 個以上持つことが分かる。よって,bcb-cnn の倍数,つまり bc(modn)b\equiv c\pmod{n} となる。

注: aa と法 pp が互いに素でないときは合同式の両辺を aa で割ってはいけません。例えば 62(mod4)6\equiv 2\pmod{4} ですが,両辺を 22 で割った式 31(mod4)3\equiv 1\pmod{4} は間違いです。

互いに素になる確率

定理3

11 以上 nn 以下の数を二つランダムに選ぶ(→注)とき,その二つの数が互いに素になる確率を pnp_n とおく。このとき limnpn=6π20.608\displaystyle\lim_{n\to\infty}p_n=\dfrac{6}{\pi^2}\simeq 0.608

注:同じ整数を二つ選ぶのもOKです。(選ぶ順番も考慮すると)全部で n2n^2 通りの場合があり,それぞれ確率 1n2\dfrac{1}{n^2} で起こります。

一部厳密ではありませんが,考え方はかなり面白いです。

説明

二つの整数 aabb が互いに素

aabb のどちらかは 22 の倍数でない,かつ
aabb のどちらかは 33 の倍数でない,かつ
aabb のどちらかは 55 の倍数でない,かつ
\cdots

ここで,nn が十分大きいとき aabb のどちらかは素数 pp の倍数でない確率は 11p21-\dfrac{1}{p^2}

よって,nn が大きいとき求める確率は(→注)

pn(1122)(1132)(1152)p_n\simeq (1-\dfrac{1}{2^2})(1-\dfrac{1}{3^2})(1-\dfrac{1}{5^2})\cdots

逆数を取って変形していく:

1pn=222213232152521=111221113211152=(1+122+1(22)2+1(22)3+)×(1+132+1(32)2+1(32)3+)×(1+152+1(52)2+1(52)3+)=k=11k2=π26\dfrac{1}{p_n}=\dfrac{2^2}{2^2-1}\cdot\dfrac{3^2}{3^2-1}\cdot\dfrac{5^2}{5^2-1}\cdots\\ =\dfrac{1}{1-\frac{1}{2^2}}\cdot\dfrac{1}{1-\frac{1}{3^2}}\cdot\dfrac{1}{1-\frac{1}{5^2}}\cdots\\ =(1+\dfrac{1}{2^2}+\dfrac{1}{(2^2)^2}+\dfrac{1}{(2^2)^3}+\cdots)\\\times(1+\dfrac{1}{3^2}+\dfrac{1}{(3^2)^2}+\dfrac{1}{(3^2)^3}+\cdots)\\\times (1+\dfrac{1}{5^2}+\dfrac{1}{(5^2)^2}+\dfrac{1}{(5^2)^3}+\cdots)\cdots\\ =\displaystyle\sum_{k=1}^{\infty}\dfrac{1}{k^2}\\ =\dfrac{\pi^2}{6}

ただし,等号の理由はそれぞれ

三つ目:無限等比級数の公式

四つ目:展開して項を比較

最後:バーゼル問題

注: aabb が「22 の倍数である」という事象,「33 の倍数である」という事象,「55 の倍数である」という事象,\cdots が互いに独立であることを使いました。

「互いに素」は「最大公約数が 11 」と同じことですが,「最大公約数が 11 」と書くよりも「互いに素」と書く方が少し楽です。

Tag:素数にまつわる覚えておくべき性質まとめ

  1. 高校数学の美しい物語
  2. 互いに素の意味と関連する三つの定理