Life is Beautiful

主に進化生物学の理論のブログです。不定期更新予定。

2つの整数が互いに素である確率

ランダムに2つの正の整数をイメージしてください。$ (a,b) $としましょう。それらで分数を作ってください。$ a/b $ですね。それがもう約分できない確率はいくらでしょうか?

0.5より大きい?小さい?

答えと証明を載せます。

命題として答えるならこうです。

「ランダムに選ばれた整数2つ $ (a,b)$ が、互いに素である確率は、$ 6/\pi^{2}$(約61% )である」。

(証明) まず$ (a,b) $が互いに素であることと、分数$ a/b $が既約分数(もう約分できない)であることは同値です。

そもそも「もう約分できない」とは、どういうことでしょう。たとえば、221/26は、13で約分できます。578/68は、34で約分できます。

前者の例と後者の例の大きな違いは、13が素数で34は合成数素数ではない)であることです。「34(=2×17)で約分できる」ということは、「"2で1回約分できる"かつ"17で1回約分できる"」ですので、約分できるかどうかで重要なのは「そもそも素数で約分できない」ということなのでしょう。

「ある整数$X$が2で約分できないならば、$X$は34でも約分できない」という命題は真ですので、最初から2で割れるかどうかを調べれば、34を含むすべての偶数に関して約分できないことについては十分なのです。

同じように、3で約分できるかどうかを調べれば、6, 9, 12といった全ての3の倍数に関して約分できないことはわかります。

4で約分できるかどうかはどうでしょう?これはすでに、2で約分できるかどうかでカバー済みですので、調べる必要がありません。

これを一般化すると、ある数$X$で約分できないことを調べるためには、その数$X$の約数について約分できないことを調べれば十分ということになります。

2以上のどんな整数も、一通りに素因数分解が可能なので、結局「所与の分数が既約である、つまり所与の分数がどんな数でも約分できないことを調べるためには、どんな素数でも約分できないことを調べれば十分である」ということになります。

ということは。

$ a/b $ が既約である確率を調べるためには、 「2で約分できない」 かつ 「3で約分できない」 かつ 「5で約分できない」 かつ …

という(互いに独立な)命題を調べ、その確率を、

「2で約分できない確率 $ Q_2 $」・・・(eq2)

× 「3で約分できない確率 $ Q_{3} $」・・・(eq3)

× 「5で約分できない確率 $ Q_{5} $」・・・(eq5)

× …

素数 $ p $ で約分できない確率 $Q_{p} $」・・・(eq.$ p $)

×…

というふうに計算すればよいでしょう。

さて、まず前提として次のよく知られた補題を示しておきます。

補題1)

素数は無限個、存在する。

 (∵)有限個しか存在しないと仮定します。このとき、最も大きな素数を$ P $と書くと、この$ P $より大きい数である \begin{align} P!+1 \end{align} は、$ P $を含むそれ以下のあらゆる素数について、割り切れません(全否定)。なぜなら、2で割っても、3で割っても、5で割っても、1余りますが、 $ P$以下の全ての素数で割ろうとしたときについて、おなじことが言えるからです。$P!+1$は、$P$以下の全ての整数$k$について、$k$で割ると1余る数ですから、素数です。この結論は、$ P $が最大の素数であるという仮定に反しますので、矛盾。したがって無限に素数は存在します。■

さて、我々は、$Q:= Q_{2} \times Q_{3} \times Q_{5} \times Q_{7} \times \dots $(あらゆる素数$p$に関する$Q_{p} $の積)を知りたいのでした。 「$a/b$ が $ p $で約分できる」とは、「$a$ も $b $ も $ p $ で割り切れる」ということです。 全て正の整数を並べてみたとき、$p$の倍数は$p$ごとに現れます($p,2p,3p,\dots$)から、 $ a $ が $ p $ で割り切れる確率は$ \frac{1}{p} $ですし、これは$b$についても同様です。よって、$ a/b $が素数 $p$で約分できる確率は、 $a$も$b$も$p$で割り切れる確率ですので、$1/p^{2}$です。

したがって、$a/b$が素数$p$で約分できない確率は \begin{align} Q_p=\left( 1-\frac{1}{p^{2}} \right) \end{align} と判ります。ということは、求めるのは

\begin{align} Q:=\prod_{p: \textrm{ prime}} \left( 1-\frac{1}{p^{2}} \right) \end{align}

ですね($\prod$は積を表し、$p: \textrm{prime}$は$p$が素数(prime number)ということを示しています)。こんな積は求められるのか…と思われるかもしれませんが、次の有名な公式があります。

補題2:オイラー積、指数2の場合)

次の公式が成立する: \begin{align} \zeta (2) :=\sum_{n=1}^\infty \frac{1}{n^{2}}=\frac{1}{Q}. \end{align}

 (∵)$ \zeta(2) $の定義式の両辺を$ 1/2^{2}$倍すると、 \begin{align} \frac{1}{2^{2}}\zeta (2) =\sum_{n=1}^\infty \frac{1}{(2n)^{2}} \end{align} が成立します。右辺は、2の倍数の平方数の逆数の和ですので、これをもとの$ \zeta (2)$から引くと、2の倍数でない数(つまり奇数)の二乗の逆数の和だけが残り、

\begin{align} \left( 1-\frac{1}{2^{2}} \right) \zeta (2) =\sum_{n: \text{odd}}^\infty \frac{1}{n^{2}} \end{align}

が得られます(oddは、奇数のこと)。同じように、更にこの両辺に$ 1-\frac{1}{3^{2}}$を掛けると、 奇数のうち3の倍数でないもの(つまり2の倍数でも3の倍数でもないもの)だけが、被和項(和をとられる項)としてのこります。 更に更に、$ 1-\frac{1}{5^{2}}$をかけると、2の倍数でも3の倍数でも5の倍数でもないものだけが残り… ということが分かります*1。 これを帰納的に繰り返すことで、「どんな素数でも割り切れない$ n $」番目の項、すなわち$ n=1$の項 $=\frac{1}{1^{2}} $だけが残り、

\begin{align} \underbrace{ \left( \prod_{p: \text{prime}} \left( 1-\frac{1}{p^{2}} \right) \right) }_{=Q} \zeta (2) =\frac{1}{1^{2}}=1 \end{align}

となります。つまり$ \zeta(2)=1/Q $です。■

では、$ Q $を知るには$ \zeta(2)$を知ればよい。そのためには…

補題3:バーゼル問題)

\begin{align} \sum_{n=1}^{\infty} \frac{1}{n^{2}}=\frac{\pi^{2}}{6} \end{align}

 (∵)$ \sin{x}$のテイラー展開は \begin{align} \sin{x}=\frac{x^{1}}{1!}-\frac{x^{3}}{3!}+\frac{x^{5}}{5!}-\dots \end{align} であるが、これを$ x \neq 0 $で割ると \begin{align} \frac{\sin{x}}{x}=1-\frac{x^{2}}{3!}+\frac{x^{4}}{5!}-\dots \end{align} が得られます。左辺は、全ての正の整数$ n $に対して、$ x= +n\pi$ と $ x= - n\pi$で0になるはずなので、$ \left( 1- \frac{x^2}{(n \pi)^2} \right) $で割り切れるはずです。よって、 \begin{align} \frac{\sin{x}}{x}= \prod_{n=1} ^{+\infty} \left( 1- \frac{x^2}{(n \pi)^2} \right)
\equiv 1-\frac{x^{2}}{3!}+\frac{x^{4}}{5!}-\dots \end{align} が成立するはずです。≡の記号は、恒等式を意味しています。よって係数比較で$ x^{2}$の項を比較すると、 \begin{align} -\frac{1}{3!}=-\sum_{n=1}^{+\infty}\left(\frac{1}{n\pi}\right) ^{2} \end{align}

が取り出せるので、両辺に$-\pi^{2}$を乗ずると結局

\begin{align} \sum_{n=1}^{\infty} \frac{1}{n^{2}}=\frac{\pi^{2}}{6} \end{align}

が得られます。■

ということで、補題1〜3より、既約分数である確率は$ Q=6/\pi^{2}$であることがわかりましたね。

なお、分母が1である場合 $ a/1 $ を既約と見なすかどうかは、問題ありません。なぜなら、分母が1であるという事情が起こる確率は0だからです。が、$b>1$に対しては $ 1/b $ を既約と見なすのは自然ですから、対称性を考慮して、$ a/1 $は既約と約束するのが美しいでしょう。1から100までの$ a,b $について、既約=青、約分可能=赤でプロットした図を乗せておきます。最終的には、青の領域の割合が$ 6/\pi^{2}$(約61%)になるということですね。

f:id:lambtani:20140808182043j:plain

*1:本当は極限操作を行なっているので、厳密にはデリケートな扱いが要求される