OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

素数の問題です

  • すぐに回答を!
  • 質問No.131899
  • 閲覧数298
  • ありがとう数8
  • 気になる数0
  • 回答数9
  • コメント数0

お礼率 86% (456/526)

素数の問題です。「次のことを示せ。2^n - 1 が素数で
あるならば、nは素数である。ただしnは自然数である。」

解答では、「nが素数でないとすると、n = kl (k,l は1より大きい自然数)とおけて、
2^n - 1 = 2^kl -1 = (2^l)^k - 1 = (2^l -1){(2^l)^k-1 +(2^l)k-2 + ・・・・・+1}
l≧2, k≧2 より、
2^l -1>1 , {(2^l)^k-1 +(2^l)k-2 + ・・・・・+1}>1 であるので、2^n - 1 は素数ではないとなっているのですが、なぜ、はじめにn = kl と置くときにk,l は1より大きい自然数とおくのでしょうか。当然k , l が1のときも考えないといけないと思うのですが。
よろしくお願いします。
通報する
  • 回答数9
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.9
レベル8

ベストアンサー率 51% (16/31)

shushouです。
私の回答は背理法を意識したものです。
対偶でも背理法でも証明できます。
対偶で証明する場合は私の回答を次のように直してください。
「対偶”nが素数でないとき、2^n-1は素数でない”を示す。
n=1のとき 2^n-1=2-1=1 となって素数でない。・・・・・・(以下同じ)」

背理法での証明も詳しく書いておきます。
「背理法で示す。
(☆)2^n-1が素数のとき、nは素数ではない
と仮定する。
(ご存知だと思いますが(☆)という仮定のもとで議論して
何らかの矛盾を出します。)
2^n-1が素数なのだからpを素数として
2^n-1=p と置く。
nは素数ではないから nは1か合成数である。
n=1のとき p=2^n-1=2-1=1 で1は素数ではないから矛盾
nが合成数のとき n = kl (k,l は1より大きい自然数)と置けて
p=2^n - 1 = 2^kl -1 = (2^l)^k - 1 = (2^l -1){(2^l)^k-1 +(2^l)^k-2 + ・・・・・+1}
l≧2, k≧2 より、
2^l -1>1 , {(2^l)^k-1 +(2^l)^k-2 + ・・・・・+1}>1 
であるので、2^n - 1 は素数ではなくなり
これは2^n-1が素数であるという仮定に反する。よって、矛盾。
なぜ矛盾が出たかというと(☆)という仮定が間違っているからである。
ゆえに、2^n-1が素数ならばnは素数である。」

まあ、対偶での証明とほとんど同じですが。

細かいことでも自分の納得するまで考える姿勢は素晴らしいと思います。
文章だとどうしても細かいニュアンスが伝えられなくて
分かりにくいところもあるかもしれません。
もしあれば遠慮なく質問してくださいね。


 
お礼コメント
s-word

お礼率 86% (456/526)

お返事ありがとうございます。背理法で証明していたのですね。なるほど、よくわかりました。ありがとうございました。
投稿日時 - 2001-09-12 07:03:08
-PR-
-PR-

その他の回答 (全8件)

  • 回答No.3
レベル13

ベストアンサー率 24% (357/1463)

背理法による証明ですね。 この証明の骨格は、2^n-1が素数の時にnが素数でない場合があるとすると矛盾が生じる ことを示すことにあります。k,lが1であることを許すと、nが素数であってもn=klとおく ことができてしまい、かならずしも矛盾するとは言えないという結論になってしまいます。 しかし、ここでは、nが素数であると仮定した場合のみ考えればよいのですから、k,lは 1より大きな自然数としてもn ...続きを読む
背理法による証明ですね。
この証明の骨格は、2^n-1が素数の時にnが素数でない場合があるとすると矛盾が生じる
ことを示すことにあります。k,lが1であることを許すと、nが素数であってもn=klとおく
ことができてしまい、かならずしも矛盾するとは言えないという結論になってしまいます。
しかし、ここでは、nが素数であると仮定した場合のみ考えればよいのですから、k,lは
1より大きな自然数としてもn=klとおくことができ、そうすれば、nが素数になる場合を
効率的に排除することができます。nの値によって、kとlの組み合わせはいくつも考え
られる場合がありますが、矛盾する条件が一つでも示せればよいので、k,lが1より大きい
として矛盾を導き出した上で、さらにkやlが1になる条件は考える必要がないのです。
補足コメント
s-word

お礼率 86% (456/526)

お返事ありがとうございます。すいません、まだよくわかりません。対偶の例として、上の例題がのっていました。背理法も対偶も同じような物かと思いますが、「nが素数でない→2^n-1が素数でない」を示せばいいと思うんです。

>k,lが1であることを許すと、nが素数であってもn=klとおくことができてしまい、

k,lが1のときはnは素数ではなくなりますよね。(k,l)=(1,3)のときはnは素数になってしまって仮定が成り立たないということでしょうか。(k,l)=(1,1)のときと、k,lが2以上の整数の場合に分けすると、nが素数でない場合が過不足なく表せると思うのですが。
投稿日時 - 2001-09-08 18:51:04

  • 回答No.2
レベル11

ベストアンサー率 44% (107/243)

前の方が答えられているように1は素数ではありません。 すべての数は素数の積であらわすことができます(素因数分解ともいいます)。 たとえば、12=2・2・3、 34=2・17といったように。 素数の定義は、1とそれ自身でしか割ることの出来ない数なので1は入れることができません。 もし狩りに1を素数に入れてしまうと、12=1・2・2・3や1・1・1・1・2・2・3 といったように12の素因数分解 ...続きを読む
前の方が答えられているように1は素数ではありません。

すべての数は素数の積であらわすことができます(素因数分解ともいいます)。
たとえば、12=2・2・3、 34=2・17といったように。
素数の定義は、1とそれ自身でしか割ることの出来ない数なので1は入れることができません。
もし狩りに1を素数に入れてしまうと、12=1・2・2・3や1・1・1・1・2・2・3
といったように12の素因数分解の結果が無限にできてしまうんですよね。
このことから考えても1は素数には入れない方がいいことがわかりますよね?
  • 回答No.1

1は素数と定義しないからじゃないですか。 定義してしまうと素数は1だけになってしまう。 ...続きを読む
1は素数と定義しないからじゃないですか。
定義してしまうと素数は1だけになってしまう。
補足コメント
s-word

お礼率 86% (456/526)

お返事ありがとうございます。nが素数でないとすると、n=klとおけると書いてあったので、この場合はnは素数でないものだと置いていると思ったのですが。
投稿日時 - 2001-09-08 18:47:51
  • 回答No.4
レベル9

ベストアンサー率 29% (14/47)

「2^n - 1 が素数で あるならば、nは素数である。ただしnは自然数である。」 ⇔「nが素数でないとき、2^n - 1は素数ではない。ただしnは自然数である」(∵対偶) だからこれを証明する。 証明 nが素数でない自然数のとき、n=KL(K,Lは自然数) と置ける。 「等比数列の公式でp≠1のとき、 1+p+p^2+p^3+…+p^(n-1)={(p^n)-1}/(p-1) ⇔( ...続きを読む
「2^n - 1 が素数で あるならば、nは素数である。ただしnは自然数である。」
⇔「nが素数でないとき、2^n - 1は素数ではない。ただしnは自然数である」(∵対偶)
だからこれを証明する。

証明
nが素数でない自然数のとき、n=KL(K,Lは自然数) と置ける。

「等比数列の公式でp≠1のとき、
1+p+p^2+p^3+…+p^(n-1)={(p^n)-1}/(p-1)
⇔(p^n)-1=(p-1){1+p+p^2+p^3+…+p^(n-1)}」なので、

2^n-1=(2^K)^(L)-1=(2^K-1){1+(2^K)+(2^K)^2+…+(2^K)^(L-2)+(2^K)^(L-1)}

K≧2かつL≧2のとき、2^n-1は1以外の数の積になるので、素数ではない。
K=1のとき、n=Lとなる。
L=1のとき、n=1なので、仮定「nが素数でない自然数のとき」に反する。
L≠1のとき、n=KLと置く意味がない。(わかるよね?そうだよね?当たり前だよね?)
よって、証明終わり。
補足コメント
s-word

お礼率 86% (456/526)

お返事ありがとうございます。
>K=1のとき、n=Lとなる。
L=1のとき、n=1なので、仮定「nが素数でない自然数のとき」に反する。

ここのところが、よくわからないのですが、
n=1のときは、仮定「nが素数でない自然数のとき」に
反するのではなくて、含まれると思ったのですが。
「1」って素数でない自然数ですよね。もしかして私スゴイ間違いしてますでしょうか(^^.)
投稿日時 - 2001-09-09 23:49:33
  • 回答No.5
レベル9

ベストアンサー率 29% (14/47)

「メルセンヌ素数」とyahooで調べるのだ。 ちなみに○ooはあまり載っていない。不便なことだぜ。ぷんぷん。 ...続きを読む
「メルセンヌ素数」とyahooで調べるのだ。
ちなみに○ooはあまり載っていない。不便なことだぜ。ぷんぷん。
お礼コメント
s-word

お礼率 86% (456/526)

ありがとうございました。行って来ました。メルセンヌ素数っていうんですね。人類って知らない間にすごいことやってたんですね。知らない世界だったので、数学の歴史を見て大変興味深かったです。
投稿日時 - 2001-09-09 23:57:59
  • 回答No.7
レベル13

ベストアンサー率 24% (357/1463)

あ、なるほど。そういう疑問だったわけですね。 「nが素数でない」←→「n=1またはn=kl(k,lは1より大きい自然数)」 ということですね。 おっしゃる通りだと思います。 解答は不完全です。 ただ、証明としては、k,lが1の場合を考えるよりも、 n=1の場合とそうでない場合を分けて、 n=1の場合は直接2^n-1が素数でない(=1)ことを示し、 それ以外の場合について解答の通りの証明 ...続きを読む
あ、なるほど。そういう疑問だったわけですね。
「nが素数でない」←→「n=1またはn=kl(k,lは1より大きい自然数)」
ということですね。
おっしゃる通りだと思います。
解答は不完全です。

ただ、証明としては、k,lが1の場合を考えるよりも、
n=1の場合とそうでない場合を分けて、
n=1の場合は直接2^n-1が素数でない(=1)ことを示し、
それ以外の場合について解答の通りの証明を行った方が楽だと思います。

P.S.
前の回答で「背理法」と書きましたが、違いましたね。
これもおっしゃる通り対偶でした。

脱帽...。
お礼コメント
s-word

お礼率 86% (456/526)

再びお返事していただいてどうもありがとうございます。

>ただ、証明としては、k,lが1の場合を考えるよりも、
n=1の場合とそうでない場合を分けて、
n=1の場合は直接2^n-1が素数でない(=1)ことを示し、
それ以外の場合について解答の通りの証明を行った方が楽だと思います。

なるほど、そうすると、断然やりやすいですね。どうも助けていただいてありがとうございました。模範解答も書き直しておきます。
投稿日時 - 2001-09-10 23:59:21
  • 回答No.6
レベル9

ベストアンサー率 43% (13/30)

「~とおく。」は数学特有の言い回しの問題で難しいですね。 結論から言えば、そう置けば証明(または問題が解ける)できるから。 の一言になるのでしょう。(笑) ただ、某問題集の解答によれば、「nが素数でない」自然数でなくとも、 n=kl(k,lは1より大きい自然数)と表されるnについて2^n-1は素数でない。 がいえます。この事実に対しては某問題集(?)の解答をs-wordさんは 納得されていると ...続きを読む
「~とおく。」は数学特有の言い回しの問題で難しいですね。
結論から言えば、そう置けば証明(または問題が解ける)できるから。
の一言になるのでしょう。(笑)
ただ、某問題集の解答によれば、「nが素数でない」自然数でなくとも、
n=kl(k,lは1より大きい自然数)と表されるnについて2^n-1は素数でない。
がいえます。この事実に対しては某問題集(?)の解答をs-wordさんは
納得されていると思います。
(n=kl(k,lは1より大きい自然数)と表される自然数n⇔nは素数でない
ですから、『「nが素数でない」自然数でなくとも』はあり得ず、
必ず「nは素数でない」になりますが。。。)

一般にnが素数でなかろうがあろうが
n=kl(k,lは自然数)の形で表すことができます。
しかし、どんな自然数もkl(k,lは1より大きい自然数)の形に表すことができるか
と問えば素直には「No」と答えるでしょう。
(少なくとも素数は定義から上のような積の形に表しえないことは自明。実は逆も言える。)

A={kl|k,lは1より大きい自然数}
P={n|nは素数でない}
とします。
Aに属する自然数nについては、2^n-1は素数ではありません。
当初の問題(の対偶ヴぁーじょん)を再掲すれば
Pに属するnについて2^n-1は素数でないことを示せ。
になりますが、P⊂A(実際は等号成立)なので(ある意味で)自明です。

というか、だからこそ
nを素数でないとすると、n = kl (k,l は1より大きい自然数)とおけて、、、
という言い回しになるのではないでしょうか。
補足コメント
s-word

お礼率 86% (456/526)

お返事どうもありがとうございます。

>某問題集の解答によれば、「nが素数でない」自然数でなくとも、
n=kl(k,lは1より大きい自然数)と表されるnについて2^n-1は素数でない。
がいえます。この事実に対しては某問題集(?)の解答をs-wordさんは
納得されていると思います。

すいません、某問題集ではないと思います。予備校のテキストの後ろの方に解答付きで載っていました。某問題集って有名な本なのでしょうか。できれば教えていただきたいのですが・・・。

>A={kl|k,lは1より大きい自然数}
P={n|nは素数でない}
P⊂A(実際は等号成立)

「n=1」の場合はPしか属さないと思ったのですが・・・。
どこか私ずれているのでしょうか・・・。
投稿日時 - 2001-09-10 00:07:39
  • 回答No.8
レベル8

ベストアンサー率 51% (16/31)

1でも素数でもない自然数のことを合成数といいます。 素数と合成数の最大の違いは何だか分かりますか。 1ではない自然数を2つの自然数の積に書いたとき (つまり、12=2×6とか17=1×17とか) 素数はどちらか一方が1に必ずなります。 合成数はどちらも1以外にすることが必ずできます。 たとえば合成数は 24=4×6、34=2×17、 のように1を含まないように書けるのに対して 素数は、3= ...続きを読む
1でも素数でもない自然数のことを合成数といいます。
素数と合成数の最大の違いは何だか分かりますか。
1ではない自然数を2つの自然数の積に書いたとき
(つまり、12=2×6とか17=1×17とか)
素数はどちらか一方が1に必ずなります。
合成数はどちらも1以外にすることが必ずできます。
たとえば合成数は 24=4×6、34=2×17、
のように1を含まないように書けるのに対して
素数は、3=1×3、19=1×19
というように必ず1を含みますね。
だから、
合成数=(1より大きい自然数)×(1より大きい自然数)
と書けます。

さて、s-wordさんの
>当然k , l が1のときも考えないといけないと思うのですが
という疑問について。
このような疑問が浮かぶのは(とても素晴らしいことです)
解答に不備があるからです。
解答の
”nが素数でないとすると、n = kl (k,l は1より大きい自然数)とおけて”
の部分を次のように直しましょう。
”nが1でも素数でもないとすると、n = kl (k,l は1より大きい自然数)とおけて”

nが1でも素数でもないとするとnは合成数となりますから
これなら納得できるのではないでしょうか。
そして解答を次のようにします。
「n=1のとき 2^n-1=2-1=1 となって素数でないから矛盾。
nが1でも素数でもないとすると、n = kl (k,l は1より大きい自然数)とおけて
・・・・・・(以下同じ)」

n = kl (k,l は1より大きい自然数)とおくと
n=1の場合がぬけてしまうので
n=1の場合は実際に代入して調べてしまおう、
というわけです。
お礼コメント
s-word

お礼率 86% (456/526)

お返事どうもありがとうございます。なるほど、解答に不備があったのですね。

>n=1の場合は実際に代入して調べてしまおう、
というわけです。

なるほど、そうすると、n=kl とおけることも納得できました。そして、n=1 を代入したときに、

>「n=1のとき 2^n-1=2-1=1 となって素数でないから矛盾。

とあるのですが、すいません、「矛盾」というのがよくわかりません。「矛盾」ではなくて、2^n-1=2-1=1 となって素数でないからその対偶の、「2^n - 1 が素数で あるならば、nは素数である。」が成立するということを表しているということだと思うのですが。仮定は、「nが1でも素数でもないとすると」だから、2^n-1が素数であると仮定した訳ではないと思うのですが。問題文の仮定は、「2^n - 1 が素数であるならば、nは素数である。」という仮定で、解答では、違う視点から、違う仮定を立てて証明するという方法だと思うので、どこと矛盾が起きているのかよくわかりません。もしよろしければ、お返事いただけますでしょうか。お返事どうもありがとうございました。
投稿日時 - 2001-09-10 23:53:23
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ