質問: オイラー関数についての質問なのですが写真の定理の証明の仕方がわかりません。どなたかお願いします。f(n)はオイラー関数を定義しています。
回答: n=p^k*q^l*r^m の場合、1からnまでの整数のうち、nと互いに素 である整数 は pでもqでもrでも割れない整数です。なので、 pかqかrで割れる整数の個数を数えて、nから引けばよいです。 1 から n までに pの倍数は n/p 個、q の倍数は n/q 個、r の倍数は n/r 個あります。これらの中には pq の倍数も含まれ( n/(pq)個 あります)、pとq それぞれの倍数として2重に数えられています。 qr, rp の倍数についても同じく2重に数えられています。なので、 1から n までで、p,q,r のどれかで割れる整数は、 n/p + n/q + n/r - n/(pq) -n/(qr) - n/(rp) となりそうですが、1からnまでに整数の中には、pqrで割れるものも あり、これはそれぞれ p,q,r の倍数として3重に数えてますが、これら は、pq, qr, rp の倍数でもあるので、上式で3回引き算されています。 つまり、pqrの倍数は一回も数えられていないので、1回分加える必要 があります。この辺は、p,q,r の倍数の集合それぞれを、3つの輪が 重なるべン図を書くと重なり具合が分かりやすいかと。和集合の要素 の個数が求めたいもの。)つまり、p,q,r のどれかで割れる数の個数は、 n/p + n/q + n/r - n/(pq) -n/(qr) - n/(rp) + n/(pqr) であり、これを 1から n の全体のn個から引けば、nと互いに素な 整数の個数になります。 f(n)= n - (n/p + n/q + n/r - n/(pq) -n/(qr) - n/(rp) + n/(pqr)) =n(1 -1/p -1/q -1/r +1/(pq) +1/(qr) +1/(rp) -1/(pqr)) =n*(1 -1/p)(1 -1/q)(1 -1/r) =p^k*q^l*r^m*(1 -1/p)(1 -1/q)(1 -1/r).