Page List

Search on the blog

2011年7月18日月曜日

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

最近、オイラー関数(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で割れない確率)

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

0 件のコメント:

コメントを投稿