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

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

互いに素とは

互いに素の定義

互いに素とは,2つの整数の共通の約数が 11 だけである という状況を表します。

互いに素な例

991010 は互いに素です。なぜなら,

  • 99 の約数は 1,3,91,3,9
  • 1010 の約数は 1,2,5,101,2,5,10

で,共通の約数が 11 だけだからです。

互いに素でない例

6699 は互いに素ではありません。なぜなら,両方とも 33 の倍数であり,33 が共通の約数になっているためです。

ちなみに,互いに素の定義は「共通の約数が 11 だけ」ですが,他にもいろいろな言い方があります:

  • 公約数が 11 のみ
  • 最大公約数が 11
  • 「どちらも dd の倍数」となる2以上の整数 dd は存在しない

連続する整数は互いに素

互いに素に関連する定理を紹介します。

定理1

連続する2つの整数は互いに素である。

例えば,さきほどの例で見たように 991010 は互いに素でした。このように,連続する2つの整数は互いに素になります。999999991000010000 も互いに素です!

証明

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

dd の倍数どうしの差も dd の倍数なので,(n+1)n=1(n+1)-n=1dd の倍数となる。これは d2d\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=a(bc)ab-ac=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 を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 以下の数を2つランダムに選ぶ(→注)とき,その二つの数が互いに素になる確率を pnp_n とおく。このとき limnpn=6π20.608\displaystyle\lim_{n\to\infty}p_n=\dfrac{6}{\pi^2}\fallingdotseq 0.608

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

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

説明

2つの整数 aabb が互いに素

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

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

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

pn(1122)(1132)(1152)p_n\fallingdotseq \left(1-\dfrac{1}{2^2}\right)\left(1-\dfrac{1}{3^2}\right)\left(1-\dfrac{1}{5^2}\right)\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\\ =\left\{1+\dfrac{1}{2^2}+\dfrac{1}{(2^2)^2}+\dfrac{1}{(2^2)^3}+\cdots\right\}\\ \:\times\left\{1+\dfrac{1}{3^2}+\dfrac{1}{(3^2)^2}+\dfrac{1}{(3^2)^3}+\cdots\right\}\\ \:\times \left\{1+\dfrac{1}{5^2}+\dfrac{1}{(5^2)^2}+\dfrac{1}{(5^2)^3}+\cdots\right\}\cdots\\ =\displaystyle\sum_{k=1}^{\infty}\dfrac{1}{k^2}\\ =\dfrac{\pi^2}{6}

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

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

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

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