整数論の問題です.
整数論の問題です. π(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 この最後の不等式が成り立つことがわかりません. φはオイラーのφ関数です.
ベストアンサー
区間 1≦x < k においてkと互いに素なものはφ(k)個. kと互いに素かどうかは、mod kできまる。 1≦x ≦qk +r を上のような区間 1≦x <k, k≦x < 2k, ,,, (q-1)k≦x< qk, qk<x ≦qk+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と互いに素であるものがあるということでいいですかね?
質問者からのお礼コメント
ご回答ありがとうございます. 疑問が晴れました.
お礼日時：2018/5/16 14:59
