解決済み
オイラー関数について
f(n)=p^k•q^l•r^m(1-1/p)(1-1/q)(1-1/r)
の証明を高校の範囲での証明がわかりません。
ベストアンサー
厳密な証明ではないですが、考え方のヒントとしてどうぞ
任意の自然数を選択した際、それがj(自然数)の倍数である確率は1/j。
故にjの倍数でない確率は1-1/j(←余事象の考え方)。特にjが素数である場合、これはjと互いに素である確率を示す。
よってn個の自然数の中からjの倍数でない数の個数は
n(1-1/j)と表される。
p^k·q^l·r^m以下の自然数の中で、p(素数)と互いに素である数の個数は
p^k·q^l·r^m·(1-1/p)･･･①
さらにこの数からqと互いに素な数の個数を求めるには、
①×(1-1/q) とすれば良い。
これをさらにrでも行えば例の式が得られる。
