![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
整数論の問題です.
π(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 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
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
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 0でも無限でもない。 4 2023/04/22 19:12
- 数学 正の約数の個数が20個である最小の自然数を求めよ」 という問題で、(□+1)×(△+1)=20となる 4 2022/07/26 11:58
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 某大学の数学入試問題で、フェルマーの定理絡みの問いがありました。 9 2023/02/14 08:35
- 化学 化学基礎 イオン反応式 Al + H+ →Al3+ + H2 回答 2Al + 6H+ → 2Al3 1 2022/11/27 20:10
- 数学 数学の問題についてです。 この問題は背理法による証明の問題なのですが、 写真右上の赤線「rを有理数と 2 2022/06/28 16:28
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- 教育学 数学の問題についてです。 この問題は背理法による証明の問題なのですが、 写真右上の赤線「rを有理数と 1 2022/06/28 16:26
- 数学 2次以上の多項式g(x)であって, 任意の無理数に対して無理数の値を取るものは存在しないことを示せ. 8 2022/06/27 11:28
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
(1+h)^n≧1+nh+{n(n-1)/2}h^2
-
なぜ等号は常に成り立たないの...
-
数学的帰納法 不等式の証明
-
nの階乗と2のn乗の比較
-
√2,√3,√5,√6,√7,√10は有理数体...
-
(b+c)(c+a)(a+b)≧8abc
-
数学IIの問題です 0≧xのとき、...
-
問題の意味すらわかりません
-
数学的帰納法の問題
-
急いでいます 数学の問題
-
(2n+1)!!・n!・2^n=(2n)!
-
数II a^2−ab+b^2≧a+b−1の不等式...
-
不等式の証明と絶対値記号
-
数学的帰納法の不等式について...
-
整数論の問題です. π(x)=o(x)の...
-
大小関係
-
変数の関係に相加相乗平均を使...
-
証明が合っているかどうか?
-
不等式の証明(テイラー展開)
-
この数学の問題が解けません。...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
なぜ等号は常に成り立たないの...
-
nの階乗と2のn乗の比較
-
部分分数分解について。 1/a・b ...
-
||a+b|| ≦ ||a|| +||b||の証明
-
数学的帰納法 不等式の証明
-
無理数から無理数を引いた結果...
-
絶対値の不等式の証明ができません
-
(b+c)(c+a)(a+b)≧8abc
-
証明が合っているかどうか?
-
不等式の証明(テイラー展開)
-
数学的帰納法
-
問題の意味すらわかりません
-
述語について成り立つ関係
-
(n!)^2≧n^n(nは自然数)
-
証明の問題なのですが・・・
-
√11の連分数表示
-
「次の不等式を証明せよりまた...
-
√2,√3,√5,√6,√7,√10は有理数体...
-
数学の問題!
-
数学です。2番と3番の等号成立...
おすすめ情報