スポンサーサイト

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

2^m±1が素数になるためのmの条件

Fermat 数, Mersenne 数に関連する話。

2012 年 8 月 20 日更新。

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

[命題] $m$ を正の整数とする. $2^{m}+1$ が素数ならば, ある整数 $n\geq 0$ が存在して $m=2^{n}$.

[証明] 対偶を示す. $m$ が $2^{n}$ ($n\geq 0$) の形で表されないとすると, $m$ は奇数の素因数 $q$ をもつ. $X=2^{m/q}$ とおくと, \begin{align*} &2^{m} + 1 = X^{q} + 1 = (X+1)(X^{q-1}-X^{q-2}+\cdots-X+1), \\ &1<X+1<2^{m}+1. \end{align*} ゆえに, $2^{m}+1$ は合成数である. (証明終)

[命題] $m$ を正の整数とする. $2^{m}-1$ が素数ならば, $m$ は素数である.

[証明] 対偶を示す. $m=1$ のとき, $2^{m}-1=1$ は素数でない. $m$ が合成数のとき, ある整数 $b$, $c$ が存在して, $$ m = bc,\quad 1<b<m,\quad 1<c<m. $$ $X=2^{b}$ とおくと, \begin{align*} &2^{m}-1 = X^{c}-1 = (X-1)(X^{c-1}+X^{c-2}+\cdots+X+1), \\ &1<X-1<2^{m}-1. \end{align*} ゆえに, $2^{m}-1$ は合成数である. (証明終)

類似の命題

[命題] $m\geq 1$, $a\geq 2$ を整数とする. このとき, $a^{m}+1$ が素数ならば, $a$ は偶数で, ある整数 $n\geq 0$ が存在して $m=2^{n}$.

[証明] $a^{m}+1$ が素数であると仮定する.

もし仮に $a$ が奇数であるとすると, $a^{m}+1$ は偶数であるから, $a^{m}+1=2$. ところが, $m\geq 1$, $a\geq 2$ より $a^{m}+1\geq 3$. これは矛盾である. ゆえに, $a$ は偶数である.

もし仮に $m$ が $2^{n}$ ($n\geq 0$) の形で表されないとすると, $m$ は奇数の素因数 $q$ をもつ. $X=a^{m/q}$ とおくと, \begin{align*} &a^{m} + 1 = X^{q} + 1 = (X+1)(X^{q-1}-X^{q-2}+\cdots-X+1), \\ &1<X+1<a^{m}+1. \end{align*} ゆえに, $a^{m}+1$ は合成数である. これは $a^{m}+1$ が素数であるという仮定に反する. (証明終)

[例] $a=6$, $m=2$ のとき, $a^{m}+1=37$ は素数である.

[命題] $m\geq 2$, $a\geq 2$ を整数とする. このとき, $a^{m}-1$ が素数ならば, $a=2$ かつ $m$ は素数である.

[証明] $a^{m}-1$ が素数であると仮定する.

$a^{m}-1$ を因数分解すると, $$ a^{m}-1 = (a-1)(a^{m-1}+a^{m-2}+\cdots+a+1). $$ これが素数であるから, $a - 1 = \pm 1$ または $a^{m-1}+a^{m-2}+\cdots+a+1 = \pm 1$ である. $a\geq 2$, $m\geq 2$ より $a-1\geq 1$ かつ $a^{m-1}+a^{m-2}+\cdots+a+1>1$ であるから, $a-1=1$. すなわち, $a=2$.

もし仮に $m$ が合成数だとすると, ある整数 $b$, $c$ が存在して, $$ m = bc,\quad 1<b<m,\quad 1<c<m. $$ $X=2^{b}$ とおくと, \begin{align*} &2^{m}-1 = X^{c}-1 = (X-1)(X^{c-1}+X^{c-2}+\cdots+X+1), \\ &1<X-1<2^{m}-1. \end{align*} ゆえに, $2^{m}-1$ は合成数である. これは矛盾である. (証明終)

[注意] $a=3$, $m=1$ のとき, $a^{m}-1=2$ となる.

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

プロフィール

よしいず

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

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

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

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

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

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