前回オイラーのφ関数Ⅰで乗法性 \( \phi \left(\mathit{ab}\right)=\phi \left(a\right)･\phi \left(b\right) \) を示しましたが, この式と以下に述べる
\( \displaystyle\phi \left({p}^{e}\right)={p}^{e}\left(1-\frac{1}{p}\right) \) を用いると \( \displaystyle\phi \left(n\right)=n\left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \)
という 関係式が導かれます. 実際の計算ではこの式を使うと楽になります.
そしてこの式を眺めていると何となく余事象の確率っぽく見えてしまうのですが・・・
注*上の各式において
証明すること----------------------------------------------
自然数 \( n \) の素因数を \( {p}_{\mathrm{1,}}{p}_{\mathrm{2,}}\cdots ,{p}_{i} \) とするとき,
\( \displaystyle\phi \left(n\right)=n\left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \)
が成立する｡
[証明]
まず \( n={p}^{e} \) となる場合（ \( p \) は素数）
\( p \) は素数だから \( {p}^{e} \) と互いに素でない数は
\( p\times \mathrm{1}, \ p\times \mathrm{2}, \ p\times \mathrm{3}, \ ･････, \ p\times {p}^{e-1} \)の \( {p}^{\left(e-1\right)} \) 個.
よって \( {p}^{e} \) と互いに素なものの個数 \( \phi \left({p}^{e}\right) \) は
\( \displaystyle\phi \left({p}^{e}\right)={p}^{e}-{p}^{e-1}={p}^{e}\left(1-\frac{{p}^{e-1}}{{p}^{e}}\right)={p}^{e}\left(1-\frac{1}{p}\right) \)
となります.
これと前回の「オイラーの''φ''関数Ⅰ」で示した乗法性 \( \phi \left(\mathit{ab}\right)=\phi \left(a\right)･\phi \left(b\right) \) (ただし \( a,b \) は互いに素) を使うと以下のようになります.
\( n \) を素因数分解して \( n={p}_{1}^{{e}_{1}}\cdot {p}_{2}^{{e}_{2}}\cdots {p}_{i}^{{e}_{i}} \) となったとします.
このとき
\begin{align*} \phi \left( n\right) &= \phi \left({p}_{1}^{{e}_{1}}\right)\cdot \phi \left({p}_{2}^{{e}_{2}}\right)\cdots \phi \left({p}_{i}^{{e}_{i}}\right) \\ &= {p}_{1}^{{e}_{1}}\left( 1-\frac{1}{{p}_{1}}\right)\cdot{p}_{2}^{{e}_{2}}\left( 1-\frac{1}{{p}_{2}}\right)\cdots {p}_{i}^{{e}_{i}}\left( 1-\frac{1}{{p}_{i}}\right) \\ &= \left({p}_{1}^{{e}_{1}}\cdot{p}_{2}^{{e}_{2}}\cdots {p}_{i}^{{e}_{i}}\right)\cdot\left( 1-\frac{1}{{p}_{1}}\right)\cdot \left( 1-\frac{1}{{p}_{2}}\right)\cdots\left( 1-\frac{1}{{p}_{i}}\right) \\ &= n\cdot\left( 1-\frac{1}{{p}_{1}}\right)\cdot \left( 1-\frac{1}{{p}_{2}}\right)\cdots \left( 1-\frac{1}{{p}_{i}}\right). \end{align*}
ということで証明できました.
\( 0 \) から \( n \) までの, \( n \) と互いに素な数の個数の例
\( 30 \) と互いに素な数は \( 30=2\times 3\times 5 \) なので
\( \displaystyle\phi \left(30\right)=\phi \left(2\times 3\times 5\right)=30\left(1-\frac{1}{2}\right)\cdot \left(1-\frac{1}{3}\right)\cdot \left(1-\frac{1}{5}\right)=8 \)
\( 8 \) 個.
\( 600 \) と互いに素な数は \( 600={2}^{3}\times 3\times {5}^{2} \) なので
\( \displaystyle\phi \left(600\right)=\phi \left({2}^{3}\times 3\times {5}^{2}\right)=600\left(1-\frac{1}{2}\right)\cdot \left(1-\frac{1}{3}\right)\cdot \left(1-\frac{1}{5}\right)=160 \)
\( 160 \) 個.
\( \displaystyle\phi \left(n\right)=n\left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \)
この式を眺めてると, 余事象の確率に見えてきました. さらに \( n \) を掛けてるところから期待値？っぽくも見えてきます. \( 1 \) から \( n \) までの数が書いてあるサイコロを振ったとき出る目が \( n \) と互いに素である数の期待値は？という感じでしょうか.
\( \displaystyle\phi \left(n\right)=n\left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \) の一歩手前(もしくは２歩手前)は
\( \displaystyle\phi \left(n\right)={p}_{1}^{{e}_{1}}\left(1-\frac{{p}_{1}^{{e}_{1}-1}}{{p}_{1}^{{e}_{1}}}\right)\cdot {p}_{2}^{{e}_{2}}\left(1-\frac{{p}_{2}^{{e}_{2}-1}}{{p}_{2}^{{e}_{2}}}\right)\cdots {p}_{i}^{{e}_{i}}\left(1-\frac{{p}_{i}^{{e}_{i}-1}}{{p}_{i}^{{e}_{i}}}\right) \) でした.
とりあえず \( i=3 \) としてみると, \( n={p}_{1}^{{e}_{1}}\cdot {p}_{2}^{{e}_{2}}\cdot {p}_{3}^{{e}_{3}} \) で ,
\( \displaystyle\phi \left(n\right)={p}_{1}^{{e}_{1}}\left(1-\frac{{p}_{1}^{{e}_{1}-1}}{{p}_{1}^{{e}_{1}}}\right)\cdot {p}_{2}^{{e}_{2}}\left(1-\frac{{p}_{2}^{{e}_{2}-1}}{{p}_{2}^{{e}_{2}}}\right)\cdot {p}_{3}^{{e}_{3}}\left(1-\frac{{p}_{3}^{{e}_{3}-1}}{{p}_{3}^{{e}_{3}}}\right) \) です.
上の式の \( \displaystyle\left(1-\frac{{p}_{1}^{{e}_{1}-1}}{{p}_{1}^{{e}_{1}}}\right) \) だけを取り出して余事象の確率を頭に浮かべながら見てみると,
この式が \( 1 \) ~ \( {p}_{1}^{{e}_{1}} \) の中から \( {p}_{1}^{{e}_{1}} \) と互いに素な数を引き当てる確率になっているように見えます.
そしてそれらの積 \( \displaystyle\left(1-\frac{{p}_{1}^{{e}_{1}-1}}{{p}_{1}^{{e}_{1}}}\right)\cdot \left(1-\frac{{p}_{2}^{{e}_{2}-1}}{{p}_{2}^{{e}_{2}}}\right)\cdot \left(1-\frac{{p}_{3}^{{e}_{3}-1}}{{p}_{3}^{{e}_{3}}}\right) \) は, \( n={p}_{1}^{{e}_{1}}\cdot {p}_{2}^{{e}_{2}}\cdot {p}_{3}^{{e}_{3}} \)
であることを思い出すと, \( n \) と互いの素な数を引き当てる確率と解釈できます.(補足参照)
そしてこれにさらに \( n \) を掛けたものが \( \phi \left(n\right) \) となるわけですが・・・
\( 1 \) ~ \( n \) までの数から \( n \) と互いの素な数を引き当てる確率に \( n \) を掛けると何が出るのか？
単純に期待値でいいのか？ \( \phi \left(n\right) \) が期待値？ いまいちイメージが頭に浮かばないですが･･･
何が問題かというと, 個数のイメージと期待値のイメージがつながらないのです.
なのでこう考えることにします.
つまり \( 1 \) から \( n \) までの \( n \) 個の数の中に \( \displaystyle \left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \) の比率で
\( n \) と互いに素な数が存在するとするわけです(式はもとの \( i \) の式に戻ってます).
そうすると \( \displaystyle\phi \left(n\right)=n\left(1-\frac{1}{{p}_{1}}\right)\left(1-\frac{1}{{p}_{2}}\right)･･･\left(1-\frac{1}{{p}_{i}}\right) \) の式がなんとなく身近に見えてきます.
ただし, 今言ってきたことはあくまでイメージで, 個人的にそう見えるというだけで, 証明したわけではありません. ただこの式を覚えるときのイメージとしてはいいのではないかと思います.
互いに素な数 \( a,b,c \) があり, それらと互いに素でない数の集合をそれぞれ \( A,B,C \) とすると \( \overline{A\cup B\cup C}=\overline{A}\cap \overline{B}\cap \overline{C} \) なのでそれらの個数についても同様な式が成り立ち, そのことからそれらの確率についても同様とし, 積 \( \mathit{abc} \) と互いに素な数を引き当てる確率 \( P \) は
\( P\left(\overline{A}\cap \overline{B}\cap \overline{C}\right)=P\left(\overline{A\cup B\cup C}\right)=P\left(1-A\cup B\cup C\right) \) であると考えました.
オイラーのφ関数そのものというよりも, 式の形が確率っぽいのが気になって文章にしてみましたが, 確率というよりは比率と考えた方がわかりやすいようです. 厳密さよりイメージ優先という観点からはいいのではないでしょうか.