読者です 読者をやめる 読者になる 読者になる

Life is Beautiful

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

整数同士の分数が既約分数である確率

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

友人がツイート(非公開)していたので、ああ面白い、と思って考えてみました(友人は答えも一緒につぶやいていた)が、いくらでしょうか?0.5より大きい?小さい?答えと証明を載せます。

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

「ランダムに選ばれた整数2つ \( (a,b)\) で書かれた分数 \( a/b \) がもう約分できない確率は、\( 6/\pi^{2}\)である」。

(証明) まず闇雲にトライする前に、考えてみたいことがあります。「もう約分できない」(=既約である)とは、どういうことでしょう。たとえば、221/26は、13で約分できます。578/68は、34で約分できます。前者と後者の最も大きな違いは、13が素数で34は合成数*1であるということです。「34で約分できる」=「"2で約分できる"かつ"17で約分できる"」ですので、既約であるうえで重要なのは「そもそも2で約分できない」ということです。

つまり、「2で約分できないならば、自動的に・必然的に、34でも約分できない」という命題は真ですので、最初から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 \)が最大の素数であるという仮定に反しますので、矛盾。したがって無限に素数は存在します。■

さて、ということは我々は、 \begin{align} Q:=\prod_{p:\textrm{ prime}} Q_p \end{align} を知りたいわけです。「\(a/b\) が \( p \)で約分できない」とは、「\(a\) も \(b \) も \( p \) で割り切れない」ということですから、\( a \) が \( p \) で割り切れない確率\( 1-\frac{1}{p} \)に、\( b \) が \( p \) で割り切れない確率\( 1-\frac{1}{p} \)を掛けると、\( a/b \)が素数 \(p\)で約分できない確率 \( Q_p \)は \begin{align} Q_p=(1-\frac{1}{p})^{2} \end{align} と判ります。ということは、求めるのは

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

ですね。こんな積は求められるのか…と思われるかもしれませんが、次の有名な公式があります。

補題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} (1-\frac{1}{2^{2}})\zeta (2) =\sum_{n=1}^\infty \frac{1}{(2n-1)^{2}} \end{align}

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

\begin{align} 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!}-... \end{align} であるが、これを\( x \neq 0 \)で割ると \begin{align} \frac{\sin{x}}{x}=1-\frac{x^{2}}{3!}+\frac{x^{4}}{5!}-... \end{align} が得られます。左辺は、全ての正の整数\( n \)に対して、\( x= +n\pi\) と \( x= - n\pi\)で0になるはずなので、\( (x^{2}-n^{2}\pi^{2})\)で割り切れるはずです。よって、 \begin{align} \frac{\sin{x}}{x}=\prod_{n=1}^{\infty} \Bigl(1-\bigl(\frac{x}{n\pi}\bigl)^{2}\Bigl)\equiv 1-\frac{x^{2}}{3!}+\frac{x^{4}}{5!}-... \end{align} が成立するはずです。≡の記号は、恒等式を意味しています。よって係数比較で\( x^{2}\)の項を比較すると、 \begin{align} -\frac{1}{3!}=-\sum\bigl(\frac{1}{n\pi}\bigl)^{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だからです(測度0)。 が、\(b>1\)に対しては \( 1/b \) を既約と見なすのは自然ですから、対称性を考慮して、\( a/1 \)は既約と約束するのが美しいでしょう。1から100までの\( a,b \)について、既約=青、約分可能=赤でプロットした図を乗せておきます。最終的には、青の領域の割合が\( 6/\pi^{2}\)(約61%)になるということですね。

f:id:lambtani:20140808182043j:plain

*1:合成数とは、1でも素数でもない正の整数のこと

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