オイラー関数の公式の確率的意味

最近、オイラー関数（Euler's totient function）について少し復習してみた。新しい発見があったのでメモしておく。

オイラー関数とは、

と素因数分解できるある自然数nに対して、

と表され、これはn未満の自然数でnと互いに素なものの数を表しています。

　上記の公式の証明は、以下3つの補題から簡単にできます。

1番目の補題は、pが素数なことから自明。2番目の補題は、p^k未満の数でpを素因数にもつものを数えれば導出できます。3番目の補題は、aと因数を共有しないもの、bと因数を共有しないものを、それぞれaとbの法を元に列挙して、中国の剰余定理を使えば証明できます。

これら3つの補題からオイラー関数の公式は導出可能ですが、詳細は省略。

面白いと思ったのは、オイラー関数を

(n未満のnと互いに素な自然数の個数)

= (1-nまでの自然数の個数)

* (1-nまで自然数のp1で割れない確率)

* (1-nまで自然数のp2で割れない確率)

.....

* (1-nまで自然数のpkで割れない確率)

と捉えることができるということです。確かに言われてみればその通りですが、この発想は面白いと思いました。