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

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

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

$ab\equiv ac\pmod{n}$ のとき，

$ab-ac=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$ を1つも持たない

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

同様に $i=2,\cdots, k$ に対しても，$(b-c)$ が素因数 $p_i$ を $e_i$ 個以上持つことが分かる。よって，$b-c$ が $n$ の倍数，つまり $b\equiv c\pmod{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\fallingdotseq \left(1-\dfrac{1}{2^2}\right)\left(1-\dfrac{1}{3^2}\right)\left(1-\dfrac{1}{5^2}\right)\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\\ =\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}$

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

• 3つ目：無限等比級数の公式
• 4つ目：展開して項を比較
• 最後：バーゼル問題