スポンサーサイト

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

nの平方根とnの間に素数が存在する

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

[補題] $p$ を素数, $\displaystyle\binom{n}{k}$ を二項係数とし, $e(p)$ を $\displaystyle\binom{n}{k}$ の $p$ 指数とする. このとき, $p^{e(p)}\leq n$ が成り立つ.

[証明] 関連記事を参照.

[補題] $n$, $k$ を整数とし, $2\leq k\leq n$ を満たすとする. このとき, $$ \left(\frac{n}{k}\right)^{k}<\binom{n}{k} $$ が成り立つ.

[証明] 各 $i=1$, $2$, $\ldots$, $k-1$ に対して $$ \frac{n-i}{k-i}-\frac{n}{k} = \frac{(n-k)i}{(k-i)k} > 0 $$ であるから, $$ \binom{n}{k} = \prod_{i=0}^{k-1}\frac{n-i}{k-i} > \left(\frac{n}{k}\right)^{k} $$ となる. (証明終)

実数 $x$ に対し, $x$ を超えない最大の整数を $\lfloor x\rfloor$ で表す. また, $x$ 以下の素数の個数を $\pi(x)$ で表す.

[補題] 任意の実数 $x\geq 8$ に対して, $\pi(x)\leq x/2$ が成り立つ.

[証明] まず, 任意の整数 $k\geq 8$ に対して, $\pi(k)\leq k/2$ となることを示す. $\pi(8)=4$ は直接確かめられる. $k\geq 9$ なる任意の整数 $k$ に対して, $1$ は素数でなく, $2$ の倍数は ($2$ 自身を除き) 合成数であり, $9=3^{2}$ も合成数であるから, それらを差し引けば, \begin{align*} \pi(k) &\leq k - 1 - \left(\left\lfloor\frac{k}{2}\right\rfloor - 1\right) - 1 \\ &\leq k - 1 - \left(\frac{k}{2} - 2\right) - 1 = \frac{k}{2}. \end{align*} さらに, 任意の実数 $x\geq 8$ に対して, $$ \pi(x) = \pi(\lfloor x\rfloor) \leq \frac{\lfloor x\rfloor}{2} \leq \frac{x}{2} $$ となる. (証明終)

[補題] $n$, $k$ を整数とし, $8\leq k\leq \sqrt{n}$ を満たすとする. このとき, 二項係数 $\displaystyle\binom{n}{k}$ は $k$ より大きい素因子をもつ.

[証明] 背理法により証明する. $\displaystyle\binom{n}{k}$ が $k$ より大きい素因子をもたないと仮定する.

上の補題より, 任意の素数 $p$ に対して, $e(p)$ を $\displaystyle\binom{n}{k}$ の $p$ 指数とすれば, $p^{e(p)}\leq n$ が成り立つ. また, 上の補題より, $\pi(k)\leq k/2$. すなわち, $k$ 以下の素数の個数は $k/2$ 以下である. よって, $$ \binom{n}{k} = \prod_{p\leq k}p^{e(p)}\leq n^{k/2}. $$ 一方, 上の補題より, $\displaystyle\left(\frac{n}{k}\right)^{k} < \binom{n}{k} $. ゆえに, $$ \left(\frac{n}{k}\right)^{k} < n^{k/2}. $$ すなわち, $$ n^{k/2} < k^{k}. $$ これより $\sqrt{n}<k$ が得られるが, これは $k\leq \sqrt{n}$ を満たすことに反する. (証明終)

[定理] 任意の $n>2$ に対して, ある素数 $p$ が存在して, $\sqrt{n}<p<n$ が成り立つ.

[証明] $n\geq 64$ かつ $n$ が合成数のとき. $8\leq\lfloor\sqrt{n}\rfloor\leq\sqrt{n}$ であるから, 上の補題より, 二項係数 $\displaystyle\binom{n}{\lfloor\sqrt{n}\rfloor}$ の素因子 $p$ で $\lfloor\sqrt{n}\rfloor<p$ なるものが存在する. もし仮に $p\leq\sqrt{n}$ ならば, $\lfloor\sqrt{n}\rfloor$ の最大性により $p\leq \lfloor\sqrt{n}\rfloor$ となり矛盾が生じる. ゆえに, $\sqrt{n}<p$ である. 一方, 上の補題より, 二項係数 $\displaystyle\binom{n}{\lfloor\sqrt{n}\rfloor}$ の $p$ 指数を $e(p)$ とすると, $p^{e(p)}\leq n$. ゆえに, $p\leq n$ である. $n$ は合成数だから, $p<n$ である.

$n\geq 64$ かつ $n$ が素数のとき. $n\geq 67$ である. また, $n$ は奇素数であり, $n-1$ は偶数なので合成数である. 直前の議論から, $\sqrt{n-1}<p<n-1$ を満たす素数 $p$ が存在する. $p$ は $\sqrt{n}<p<n$ も満たす. 実際, $p<n$ は明らかであり, $$ \sqrt{n-1}<p \Longrightarrow n-1<p^{2} \Longrightarrow n\leq p^{2}. $$ $n$ は素数だから, 平方数でない. よって, $n<p^{2}$. ゆえに, $\sqrt{n}<p$.

いずれにせよ, $n\geq 64$ のとき, ある素数 $p$ が存在して, $\sqrt{n}<p<n$ が成り立つ.

$n<64$ のとき. $n=3$, $4$, $\ldots$, $63$ に対して, $\sqrt{n}<p< n$ を満たす素数 $p$ を探せばよい. 実際には, $2$, $3$, $5$, $7$, $11$ のどれかが $p$ の候補になる. (証明終)

参考文献

  • P. Erdös: A Theorem of Sylvester and Schur, J. London Math. Soc. 9 (1934), 282-288.

関連記事

二項係数のp指数に関する評価

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

プロフィール

よしいず

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

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

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

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

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

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