整数論の問題です. π(x)=o(x)の証明の中でわからないところがあります. 左辺はx以下の素数の

整数論の問題です.
π(x)=o(x)の証明の中でわからないところがあります.
左辺はx以下の素数の個数で右辺はランダウの記号です.

証明
任意の自然数kを固定するとx以下の素数は以下の条件の少なくとも一つをみたす.
(A)k以下である.
(B)kと互いに素である.
すなわちk以上の自然数でkと1より大きい公約数を持つものは素数ではありえない.そういうもの以外を数えれば素数を数え上げることができるので
π(x)≦k+#{n≦x|GCD(n,k)=1}
xをkで割ったときx=qk+r (0≦r<k)とすると
π(x)≦k+qφ(k)+r

この最後の不等式が成り立つことがわかりません.
φはオイラーのφ関数です

No.1 回答者： mtrajcp 回答日時： 2018/12/15 10:53

x自然数

k自然数
Π(x)=(x以下の素数の個数)
φ(k)=(k以下のkと互いに素な自然数の個数)
とすると
Π(x)≦k+#{n≦x|GCD(n,k)=1}…(1)
xをkで割ったとき
x=qk+r(0≦r<k)
n∈{n≦x|GCD(n,k)=1}
nをkで割った時の商をm,余りをj
とすると
n=mk+j
GCD(n,k)=1だから
nとkは互いに素だから
jもkと互いに素だから
jはφ(k)通りの値をとる
n=mk+j≦x=qk+r
mk+j≦qk+r
だから
0≦m≦q
となる
m=0～q-1の時
n=mk+j
は(mはm=0～q-1のq通り)×(jはφ(k)通り)の
qφ(k)
通りある
m=qの時
n=mk+j=qk+j≦qk+r
j≦r
だから多くとも
r
通りあるからqφ(k)と合わせて多くとも
qφ(k)+r
通りあるから
∴
#{n≦x|GCD(n,k)=1}≦qφ(k)+r
↓両辺にkを加えると
k+#{n≦x|GCD(n,k)=1}≦k+qφ(k)+r
↓これと(1)から
∴
Π(x)≦k+qφ(k)+r