2015/07/24

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

分野: 整数問題  レベル: 入試対策

二つの整数 $m,n$ の最大公約数が $1$ のとき,$m$ と $n$ は互いに素(たがいにそ)であると言う。

「互いに素」に関連する定理を解説。定理1,2は基本的な内容ですが,定理3は玄人向け(美しい!)です。

互いに素について

「二つの整数の最大公約数が $1$ 」という状況は頻繁に登場するので「互いに素」と表現することが多いです(最大公約数が $1$ と書くより互いに素と書く方が少し楽)。

$3$ と $5$ の最大公約数は $1$ なので,$3$ と $5$ は互いに素。
$4$ と $6$ の最大公約数は $2$ なので,$4$ と $6$ は互いに素でない。

$n$ と $n+1$ は互いに素

定理1.
連続する二つの整数:$n$ と $n+1$,は互いに素である。

当たり前の事実ですが,整数問題でときどき活躍するので覚えておきましょう。

証明

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

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

合同式の割り算

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

定理2.
$ab\equiv ac\:\mathrm{mod}\:n$ で $a$ と $n$ が互いに素なら
$b\equiv c\:\mathrm{mod}\:n$

証明

$ab\equiv ac\:\mathrm{mod}\:n$
$\iff ab-ac$ が $n$ の倍数
$\iff a(b-c)$ が $n$ の倍数

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

  • $a(b-c)$ は素因数 $p_1$ を $e_1$ 個以上持つ
  • $a$ は $n$ と互いに素なので $a$ は素因数 $p_1$ を一つも持たない

以上より$(b-c)$ が素因数 $p_1$ を $e_1$ 個以上持つ

同様に $i=2,\cdots, k$ に対しても,$(b-c)$ が素因数 $p_i$ を $e_i$ 個以上持つことが分かる。よって,$b-c$ が $n$ の倍数,つまり $b\equiv c\:\mathrm{mod}\:n$ となる。

注:$a$ と法 $p$ が互いに素でないときは合同式の両辺を $a$ で割ってはいけません。例えば $6\equiv 2\:\mathrm{mod}\:4$ ですが,両辺を $2$ で割った式 $3\equiv 1\:\mathrm{mod}\:4$ は間違いです。

互いに素になる確率

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

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

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

(説明)
二つの整数 $a$ と $b$ が互いに素
→ $a$ と $b$ のどちらかは $2$ の倍数でない,かつ
$a$ と $b$ のどちらかは $3$ の倍数でない,かつ
$a$ と $b$ のどちらかは $5$ の倍数でない,かつ $\cdots$

ここで,$n$ が十分大きいとき $a$ と $b$ のどちらかは素数 $p$ の倍数でない確率は $1-\dfrac{1}{p^2}$

よって,$n$ が大きいとき求める確率は(→注)
$p_n\simeq (1-\dfrac{1}{2^2})(1-\dfrac{1}{3^2})(1-\dfrac{1}{5^2})\cdots$

逆数を取って変形していく:
$\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}$

ただし,等号の理由はそれぞれ
三つ目:無限等比級数の公式
四つ目:展開して項を比較
最後:バーゼル問題

注:$a$ や $b$ が「 $2$ の倍数である」という事象,「 $3$ の倍数である」という事象,「 $5$ の倍数である」という事象,$\cdots$ が互いに独立であることを使いました。

定理3を紹介したいけど記事の長さが短くなってしまので強引に定理1と2をくっつけました。

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

分野: 整数問題  レベル: 入試対策