Question

カワサキ

数Aの青チャートの重要例題114の3番の問題の解説についてです。黒い下線のようなことが言えるのは何故ですか。実際に数を代入すればそうなるのはわかるんですけど仕組みがわかりません。

(3) 1からがまでのが個の自然数のっ
ち,かの倍数はかーカ=Dが(個)ある
から,f(が)はかの倍数でないものの個数を求めて
-1
であ
に代入すると
f(がか)=Dがーが-1S
され

互いに素である自然数の個数 オイラー関数

Answer 1

✨ Best Answer ✨

安田ヒデ

具体的に考えてみれば良いと思います。
今１から１００までの自然数があった時、３の倍数はといったら100➗３=33.333で３３個です。９の倍数の数といったら100➗9 =11.111で１１個です。さらに４の倍数といったら100➗４ =25 です。５の倍数といったら100➗５ =40です。　馬鹿らしいと思ったらすみません。
ここで３や９は100の約数ではありませんので割り切れませんが倍数の数は割り算で求められます。
一方、４や５は１００の約数ですので割り切れてしかも倍数の数は割り算で求められます。

今回の場合は割り切れる場合です。1からp^kまでの自然数ということは最後がp^kで１からp^kまでの数、即ち1,2,3,4,----,p^kということです。つまり上の例だと１００がp^kの場合です。
そこにあるpの倍数の数は１００にある４や５の倍数の数を求めた時のようにP^kをPで割ればいいわけです。
即ち　P^k ➗ P　= P^(k-1)　（個）となります。

カワサキ

すごく単純で泣きそうになりました…ありがとうございます

Answer 2

としさん

pの倍数は
　p,2p,3p…,np となるので np ≦ p^k となる nを求めれば pの倍数の個数が判ります。

　n ≦ p^k / p = p^(k-1) となり、 整数nの最大値は p^(k-1) なので

p^(k-1)個 です。

カワサキ

『np ≦ p^k となる nを求めれば pの倍数の個数が判ります。』この文言がよくわからないです。理解力が足りなくて本当にごめんなさい。もう少し教えてくれませんか？

としさん

p,2p,3p,…np とすると npの nの部分は、p～np　までの個数と一致します。

p,2p,3p であれば 3pの 3 が 個数3個といった感じです。

※ pの係数を見ていると 1,2,3,4…　と なります。

これで、どうでしょうか。