素数について。

2nCnが素数Pで割れる回数はlog p2n以下であることを示せ。
ただし、pは底、2nは真数である。
この問題をご教授下さい。すみませんが。

質問者からの補足コメント

• 

  すみません。0と1 の境目をkとk＋1 で区切ったという事でしょうか？ご教授下さい。すみませんが。

  No.7の回答に寄せられた補足コメントです。 補足日時：2021/01/13 08:40

• 

  十分大きな自然数Bと、(＊B)を再考するとのBは違うものなのでしょうか？ご教授下さい。すみませんが。

    補足日時：2021/01/13 09:45

• 

  2[n/P^k] - [2n/P^k] ≦ 0.
  　2[n/P^k] - [2n/P^k] ≧ 1.
  で、これの2つの範囲を合わせて、0≦［2n／P∧k］ー2［n／P∧k］≦ 1ということでしょうか？
  ご教授下さい。すみませんが。

  No.1の回答に寄せられた補足コメントです。 補足日時：2021/01/13 22:36

No.9 ベストアンサー 回答者： ありものがたり 回答日時： 2021/01/13 19:40

＞ つまり、0になる所を、一番最後のkと次のk＋1で区切ったということでしょうか？

そのとおりです。 そう書いていますよね。

No.10 回答者： ありものがたり 回答日時： 2021/01/13 19:43

＞ 十分大きな自然数Bと、(＊B)を再考するとのBは違うものなのでしょうか？

何言ってんだ、こいつ？
(*B)の「十分大きな自然数B」がどのくらいの大きさかを考察しているのが、
「(＊B)を再考すると」の文章です。日本語が苦手なんですか？

No.8 回答者： アンドロメダシティ 回答日時： 2021/01/12 23:03

> なぜ、k＝L＋1 以降全て0になるのでしょうか？なぜ、L＋ 1なのでしょうか？

> k = L + 1 以降すべて 0 になるとすれば
と仮定している。よくわからなければ 、たとえばn = 50、P = 7 で

　　∑[k=1→∞]([2n/P^k]-[n/P^k])

を計算すること。n と P を適当に代えて10例くらい計算すればわかるだろう（笑）。

この回答へのお礼

[2n/P^L] ≧ 1
でなければならない。
のは、［2n/P∧L］は、正の整数になるからでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/13 14:56

No.7 回答者： ありものがたり 回答日時： 2021/01/12 22:47

＞ なぜ、Bを十分大きな自然数としたのでしょうか？

k を大きくしてゆくと、[ 2n/p^k ] はだんだん大きくなって
どこからか先は全部 0 になる。 だから
Σ{k=1→∞} [ m/p^k ] の Σ は k→∞ まで足す必要はなくて、
[ 2n/p^k ] が 0 でないとこだけ足しとけばいい。足すとこの
一番最後の k は、[ 2n/p^k ] ≠ 0 で [ 2n/p^(k+1) ] = 0
になるようなものであればいい。その k を B と名付けた。
よって、[ 2n/p^B ] = 1 で [ 2n/p^(B+1) ] = 0.

この回答へのお礼

つまり、0になる所を、一番最後のkと次のk＋1で区切ったということでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/13 08:36

No.6 回答者： ありものがたり 回答日時： 2021/01/12 20:56

＞ x,y は整数だからと言う所は、x = [ n/p^k ],　y = [ 2n/p^k ] だからでしょうか？

そうです。当然ですね。

この回答へのお礼

(*B)を再考すると、 B　は
[ 2n/p^B ] = 1,　[ 2n/p^(B+1) ] = 0 となるところまで小さくできる。
これは 1 ≦ 2n/p^B < 2, 0 ≦ (2n/p^B)/p < 1
で、［2n／P∧B］＝ 1、［2n／p∧(B＋ 1)］＝0となるのでしょうか？
219！は、2∧nで割れるが、2∧(n＋ 1)で割れない。でいつかは、0になるのは、分かるのですが、なぜ、Bを十分大きな自然数としたのでしょうか？もう一つ疑問があり、なぜ、B＋1 としたのでしょうか？Bは、十分大きな自然数ということは、1や2とかではない可能性もありますよね？以上2点についてご教授下さい。すみませんが。

お礼日時：2021/01/12 22:25

No.5 回答者： アンドロメダシティ 回答日時： 2021/01/12 19:37

> ∑[k=1→∞]([2n/P^k]-[n/P^k])も間違いではありませんか？

∑[k=1→∞]([2n/P^k]-2[n/P^k])

　腹を立てながら回答を書くので間違うのだwwwwwwwwwwwwwwww
　しかし、これくらいすぐわかるだろうwwwww

　元の回答者の方もわざわざ再投稿してくれたのだから削除するなよ！

この回答へのお礼

なぜ、k＝L＋1 以降全て0になるのでしょうか？なぜ、L＋ 1なのでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/12 20:26

No.4 回答者： ありものがたり 回答日時： 2021/01/12 19:23

質疑応答が続いてた質問を削除して

同じ質問を再投稿しているようなので、
昨日の回答をまた投稿しておく。

自然数 x が素数 p で割り切れる回数を Ind_p(x) と書く。
対数法則と似た Ind_p(xy) = Ind_p(x) + Ind_p(y) が成り立つ。
T = Ind_p( (2n)Cn ) ≦ log_p(2n) を示せという問題であるが、　　←(*0)
Ind の対数法則を使って、T = Ind_p( (2n)! ) - 2Ind_p(n!) である。

Ind に関して公式 Ind_p(m!) = Σ{k=1→∞} [ m/p^k ]
(ただし [ ] はガウス記号) が知られている。
x = 1,2,3,..,m を横軸上にとり、各 x の上に Ind_p(x) 個の ○ を
縦に並べた図を眺めて、○ の総数を横に束ねて集計すれば、この式が解る。
また、 k が大きくなれば [ m/p^k ] = 0 となるから、
右辺の Σ の上限は、∞ でなくとも、十分大きな自然数 B でよい。　　←(*B)
この B の大きさについては、後述する。
以上より、T = Σ{k=1..B} [ 2n/p^k ] - 2[ n/p^k ] ≦ log_p(2n)　　　←(*1)
を示す問題となった。

x = [ n/p^k ],　y = [ 2n/p^k ] と置くと、
x ≦ n/p^k < x+1,　y ≦ 2n/p^k < y+1 より
y ≦ 2n/p^k < 2(x+1) = 2x+2.
x, y は整数だから、 y ≦ 2x+1 である。
y - 2x　≦ 1 の両辺を Σ{k=1..B} すると、 T ≦ B.
以上より、 B ≦ log_p(2n) を示す問題に置き換えられた。　　←(*2)

(*B)を再考すると、 B　は
[ 2n/p^B ] = 1,　[ 2n/p^(B+1) ] = 0 となるところまで小さくできる。
これは 1 ≦ 2n/p^B < 2, 0 ≦ (2n/p^B)/p < 1 ということだから、
p ≧ 2 より、 1 ≦ 2n/p^B < 2 と整理できる。
式を変形して、log_p(n) < B　≦ log_p(2n) となる。
(*2)が示されたので、題意も示されたことになる。

この回答へのお礼

x,y は整数だからと言う所は、x = [ n/p^k ],　y = [ 2n/p^k ] だからでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/12 19:28

No.3 回答者： アンドロメダシティ 回答日時： 2021/01/12 19:14

> 2[n/P^k] - [2n/P^k] ≧ 1.と言う式は、≧ではなくて、≦ではないでしょうか？

　2[n/P^k] - [2n/P^k] ≧ -1

の間違いであった。つまり③により

　[2n/P^k] ≦ 2[n/P^k] + 1 ⇒ [2n/P^k] - 2[n/P^k] ≦ 1

この回答へのお礼

すみません。　∑[k=1→∞]([2n/P^k]-[n/P^k])も間違いではありませんか？
ご教授下さい。すみませんが。

お礼日時：2021/01/12 19:19

No.2 回答者： アンドロメダシティ 回答日時： 2021/01/12 17:57

>

https://oshiete.goo.ne.jp/qa/12133286.html
> で回答をもらっているのに、なぜ同じ質問を繰り返す？
> これはアラシ行為に等しい。
　なぜ上記のサイトを削除したのだ。
　このサイトも削除するならただちに通報する。

この回答へのお礼

すみません。　∑[k=1→∞]([2n/P^k]-[n/P^k])も間違いではありませんか？
ご教授下さい。すみませんが。

お礼日時：2021/01/12 19:18

No.1 回答者： アンドロメダシティ 回答日時： 2021/01/12 17:44

https://oshiete.goo.ne.jp/qa/12133286.html
で回答をもらっているのに、なぜ同じ質問を繰り返す？　これはアラシ行為に等しい。
　また他にも同じ質問に関して
https://oshiete.goo.ne.jp/qa/12131945.html
https://oshiete.goo.ne.jp/qa/12136116.html
のような回答をもらっているのだから、これらをもう一度よく読むこと。
　以下は元ネタの動画に沿った回答である。

　2nCn が素数 P で割れる回数は log_P(2n) 回以下である。

を証明する。

※P を底とする対数を log_P(x) で表す。
※[x] は x を超えない最大の整数である。

　　①n! が素数 P で割れる回数 ∑[k=1→∞][n/P^k]
　　②[x] + [y] ≦ [x+y]
　　③[x+y] ≦ [x] + [y] + 1

は動画や上記の複数回答で既知のはずである。

　(2n)! が素数 P で割れる回数は
　　∑[k=1→∞][2n/P^k].
　n! が素数 P で割れる回数は
　　∑[k=1→∞][n/P^k].
　したがって 2nCn = 2n!/n!n! が素数 P で割れる回数は
　　∑[k=1→∞]([2n/P^k]-2[n/P^k]).

　　x = y = n/P^k
として②③を適用すると
　　[n/P^k] + [n/P^k] ≦ [n/P^k + n/P^k] ⇔ 2[n/P^k] ≦ [2n/P^k]
　　[n/P^k + n/P^k] ≦ [n/P^k] + [n/P^k] + 1 ⇔ [2n/P^k] ≦ 2[n/P^k] + 1
であるから
　　2[n/P^k] - [2n/P^k] ≦ 0.
　　2[n/P^k] - [2n/P^k] ≧ 1.
　つまり [2n/P^k] - 2[n/P^k] は 1 か 0 のどちらかであり、
　　∑[k=1→∞]([2n/P^k]-[n/P^k])
　 = (1 or 0) + (1 or 0) + … + (1 or 0) + 0 + 0 ……
　したがって k = L + 1 以降すべて 0 になるとすれば
　　∑[k=1→∞]([2n/P^k]-[n/P^k]) ≦ 1 + 1 + … + 1 + 0 + 0 + …… = L.
　これで 2nCn が素数 P で割れる回数は L 回以下であることがわかった。あとはこの L がどんな数になるかを調べればよい。
　L を定めた条件により
　　[2n/P^L] - 2[n/P^L] ≦ 1
　　[2n/P^L] ≧ 1
でなければならない。
　　∴2n/P^L ≧ [2n/P^L] ≧ 1.
　　P^L ≦ 2n.
　　L ≦ log_P(2n).
　したがって、2nCn が素数 P で割れる回数は log_P(2n) 回以下である。

この回答へのお礼

2[n/P^k] - [2n/P^k] ≧ 1.と言う式は、≧ではなくて、≦ではないでしょうか？
間違いでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/12 18:40