重要例題１２２ 互いに素である自然数の個数ｎを自然数とするとき、ｍ≦ｎで、ｍとｎが互いに素であるような自然数ｍの個数をｆ（ｎ）とする。また、ｐ、ｑは素数とする。(２)ｐ≠ｑのとき、ｆ（ｐｑ）を求めよ。(３)自然数ｋに対し、ｆ｛ｐ（ｋ乗）｝を求めよ。この二問が数弱過ぎて、私にはとけないので解き方を教えてください。数弱なので言葉で分かりやすく説明いただけるとありがたいです。

(2)について

まずはp=2、q=3で考えてみると、n=6であり、mの候補は1〜6です。この中でmとnが互いに素となるのはm=1、5です。mを考えるときに2の倍数である数と3の倍数である数を除きましたよね。つまり、n=pqと互いに素でない数の個数をnから引くとf(n)が求められると考えられます。

1からpqの中で

(a) pの倍数である数は

p×1, p×2, ..., p×q

のq個

(b) qの倍数である数は

q×1, q×2, ..., q×p

のp個

(c) pの倍数でありqの倍数でもある数は

pqの1個

よって

f(pq)=pq-q-p+1=(p-1)(q-1)

となります。



(3)について、

p=2、k=3で考えてみると、mの候補は1〜8の8個ですが、p=2と互いに素である数は、

m=1,3,5,7

の4個です。このときも(2)と同様に2の倍数の数を除きましたよね。

では、pのk乗(以下p^k)としたときもnから、1〜p^kまでの数のうちpの倍数である数の個数を引くことで求めることができ、

1からp^kまでの数のうちpの倍数は

p×1, p×2, ..., p×p, ..., p×(p^(k-1))

のp^(k-1)個です。よって

f(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)

となります。



類題として令和6年度の大阪大学理系第5問がありますので、時間に余裕があれば目を通してみてください。