素数の問題です

質問

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

解答では、「nが素数でないとすると、n = kl (k,l は１より大きい自然数）とおけて、
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}＞１　であるので、2^n - 1 は素数ではないとなっているのですが、なぜ、はじめにn = kl と置くときにk,l は１より大きい自然数とおくのでしょうか。当然k , l が１のときも考えないといけないと思うのですが。
よろしくお願いします。

回答No.9

shushou · ベストアンサー

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

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

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

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

お礼

お返事ありがとうございます。背理法で証明していたのですね。なるほど、よくわかりました。ありがとうございました。

回答No.8

shushou

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

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

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

n = kl (k,l は１より大きい自然数）とおくと
ｎ＝1の場合がぬけてしまうので
ｎ＝1の場合は実際に代入して調べてしまおう、
というわけです。

お礼

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

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

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

＞「ｎ＝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は素数である。」という仮定で、解答では、違う視点から、違う仮定を立てて証明するという方法だと思うので、どこと矛盾が起きているのかよくわかりません。もしよろしければ、お返事いただけますでしょうか。お返事どうもありがとうございました。

回答No.7

ranx

あ、なるほど。そういう疑問だったわけですね。
「nが素数でない」←→「n=1またはn=kl(k,lは1より大きい自然数)」
ということですね。
おっしゃる通りだと思います。
解答は不完全です。

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

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

脱帽．．．。

お礼

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

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

なるほど、そうすると、断然やりやすいですね。どうも助けていただいてありがとうございました。模範解答も書き直しておきます。

回答No.6

鳴瀬 美幸（@naruse）

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

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

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

というか、だからこそ
nを素数でないとすると、n = kl (k,l は１より大きい自然数）とおけて、、、
という言い回しになるのではないでしょうか。

補足

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

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

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

＞A={kl|k,lは１より大きい自然数｝
P={n|nは素数でない}
P⊂A（実際は等号成立）

「n=１」の場合はPしか属さないと思ったのですが・・・。
どこか私ずれているのでしょうか・・・。

回答No.5

newtype

「メルセンヌ素数」とｙａｈｏｏで調べるのだ。
ちなみに○ｏｏはあまり載っていない。不便なことだぜ。ぷんぷん。

お礼

ありがとうございました。行って来ました。メルセンヌ素数っていうんですね。人類って知らない間にすごいことやってたんですね。知らない世界だったので、数学の歴史を見て大変興味深かったです。

回答No.4

newtype

「2^n - 1 が素数で あるならば、nは素数である。ただしnは自然数である。」
⇔「nが素数でないとき、2^n - 1は素数ではない。ただしnは自然数である」（∵対偶）
だからこれを証明する。

証明
ｎが素数でない自然数のとき、ｎ＝ＫＬ（Ｋ，Ｌは自然数）　と置ける。

「等比数列の公式でｐ≠１のとき、
１＋ｐ＋ｐ＾２＋ｐ＾３＋…＋ｐ＾(ｎ－１)＝｛(ｐ＾ｎ)－１｝／(ｐ－１)
⇔(ｐ＾ｎ)－１＝(ｐ－１){１＋ｐ＋ｐ＾２＋ｐ＾３＋…＋ｐ＾(ｎ－１)}」なので、

２^ｎ－１＝(２^Ｋ)^(Ｌ)－１＝（２＾Ｋ－１）｛１＋(２^Ｋ)＋(２^Ｋ)^２＋…＋(２^Ｋ)^(Ｌ－２)＋(２^Ｋ)^(Ｌ－１)｝

Ｋ≧２かつＬ≧２のとき、２^ｎ－１は１以外の数の積になるので、素数ではない。
Ｋ＝１のとき、ｎ＝Ｌとなる。
Ｌ＝１のとき、ｎ＝１なので、仮定「ｎが素数でない自然数のとき」に反する。
Ｌ≠１のとき、ｎ＝ＫＬと置く意味がない。（わかるよね？そうだよね？当たり前だよね？）
よって、証明終わり。

補足

お返事ありがとうございます。
＞Ｋ＝１のとき、ｎ＝Ｌとなる。
Ｌ＝１のとき、ｎ＝１なので、仮定「ｎが素数でない自然数のとき」に反する。

ここのところが、よくわからないのですが、
ｎ＝１のときは、仮定「ｎが素数でない自然数のとき」に
反するのではなくて、含まれると思ったのですが。
「１」って素数でない自然数ですよね。もしかして私スゴイ間違いしてますでしょうか(^^.)

回答No.3

ranx

背理法による証明ですね。
この証明の骨格は、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になる条件は考える必要がないのです。

補足

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

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

k,lが１のときはnは素数ではなくなりますよね。(k,l)=(1,3)のときはnは素数になってしまって仮定が成り立たないということでしょうか。(k,l)=(1,1)のときと、k,lが２以上の整数の場合に分けすると、nが素数でない場合が過不足なく表せると思うのですが。

回答No.2

128yen

前の方が答えられているように１は素数ではありません。

すべての数は素数の積であらわすことができます（素因数分解ともいいます）。
たとえば、１２＝２・２・３、　３４＝２・１７といったように。
素数の定義は、１とそれ自身でしか割ることの出来ない数なので１は入れることができません。
もし狩りに１を素数に入れてしまうと、１２＝１・２・２・３や１・１・１・１・２・２・３
といったように１２の素因数分解の結果が無限にできてしまうんですよね。
このことから考えても１は素数には入れない方がいいことがわかりますよね？

回答No.1

noname#3307

1は素数と定義しないからじゃないですか。
定義してしまうと素数は１だけになってしまう。

補足

お返事ありがとうございます。nが素数でないとすると、n=klとおけると書いてあったので、この場合はnは素数でないものだと置いていると思ったのですが。