スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

素数が二項係数を割るための十分条件

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

[命題] $p$ を素数, $n$, $a$ を正の整数とし, $$ \sqrt[a]{n} < p \leq\sqrt[a]{2n} $$ を満たすとする. このとき, $p$ は二項係数 $\displaystyle\binom{2n}{n}$ を割る.

[証明] まず, \begin{align*} \mathrm{ord}_{p}\left( \binom{2n}{n} \right) &= \mathrm{ord}_{p}\left( \frac{(2n)!}{(n!)^{2}} \right) \\ &= \mathrm{ord}_{p}((2n)!) - 2\mathrm{ord}_{p}(n!) \\ &= \sum_{i=1}^{\infty}\left\lfloor\frac{2n}{p^{i}}\right\rfloor - 2\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^{i}}\right\rfloor. \end{align*} $\sqrt[a]{n} < p \leq\sqrt[a]{2n}$ より $$ 0\leq\frac{n}{p^{a}}<1,\quad 1\leq \frac{2n}{p^{a}}< 2 $$ であるから, \begin{align*} \left\lfloor\frac{n}{p^{a}}\right\rfloor &= 0,\quad \left\lfloor\frac{2n}{p^{a}}\right\rfloor = 1, \\ \left\lfloor\frac{n}{p^{i}}\right\rfloor &= \left\lfloor\frac{2n}{p^{i}}\right\rfloor = 0\quad (i=a+1,\,a+2,\,\ldots). \end{align*} ゆえに, $$ \mathrm{ord}_{p}\left( \binom{2n}{n} \right) = \sum_{i=1}^{a-1}\left( \left\lfloor\frac{2n}{p^{i}}\right\rfloor - 2\left\lfloor\frac{n}{p^{i}}\right\rfloor \right) + 1. $$ 各 $i=1$, $2$, $\ldots$ に対して $$ \left\lfloor\frac{2n}{p^{i}}\right\rfloor - 2\left\lfloor\frac{n}{p^{i}}\right\rfloor\geq 0 $$ であるから, $$ \mathrm{ord}_{p}\left( \binom{2n}{n} \right) \geq 1. $$ すなわち, $p$ は $\displaystyle\binom{2n}{n}$ を割る. (証明終)

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。