整数論の問題です. π(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

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




この証明について
準備としてaとbが互いに素であるとき
aとa+bは互いに素…①
aとa-b (a>b)も互いに素…②

1≦x<kの区間でkと互いに素であるものはφ(k)個ある.
次にk≦x<2kの区間で考えると①よりφ(k)+kとkは互いに素である.よってこの区間では少なくともφ(k)個のkと互いに素であるものがあるのことがわかる.これ以外にkと互いに素であるものαがあるとすると②よりα-kもkと互いに素であるがこれはφ(k)でカウントされたものではないから矛盾.よってこのようなαは存在しないことになる.
なので各区間にはそれぞれφ(k)だけkと互いに素であるものがある。



k≦x<2kの区間で考えると①よりφ(k)+kとkは互いに素であるとありますが、φ(k)とkが互いに素であるとは限らないと思いますがこの証明は間違っているのでしょうか？また仮にあっていたとしたとしてもよってこの区間では少なくともφ(k)個のkと互いに素であるものがあるのことがわかる.とありますがなぜでしょうか？

No.1 回答者： syotao 回答日時： 2018/12/14 12:20

φ(6)＝2　のようにφ(k)とkが互いに素はかならずしもなりたたない。

だから
＜次にk≦x<2kの区間で考えると①よりφ(k)+kとkは互いに素である.＞
は
＜1≦x<kの区間でkと互いに素であるφ(k)個のαに対しｋ＋αが①よりｋと互いに素である＞
と読み換える必要がある。そうすれば
ｋ≦α＋ｋ＜2ｋ　だから
＜よってこの区間では少なくともφ(k)個のkと互いに素であるものがあることがわかる＞
は納得いきますよね。