素数の問題です。「次のことを示せ。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のときも考えないといけないと思うのですが。
よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (9件)

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は素数である。」

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

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


 
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/09/12 07:03

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の場合は実際に代入して調べてしまおう、
というわけです。
    • good
    • 0
この回答へのお礼

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

>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

あ、なるほど。

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

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

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

脱帽...。
    • good
    • 0
この回答へのお礼

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

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

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

お礼日時:2001/09/10 23:59

「~とおく。

」は数学特有の言い回しの問題で難しいですね。
結論から言えば、そう置けば証明(または問題が解ける)できるから。
の一言になるのでしょう。(笑)
ただ、某問題集の解答によれば、「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より大きい自然数)とおけて、、、
という言い回しになるのではないでしょうか。

この回答への補足

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

>某問題集の解答によれば、「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
    • good
    • 0

「メルセンヌ素数」とyahooで調べるのだ。


ちなみに○ooはあまり載っていない。不便なことだぜ。ぷんぷん。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/09/09 23:57

「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と置く意味がない。(わかるよね?そうだよね?当たり前だよね?)
よって、証明終わり。

この回答への補足

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

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

補足日時:2001/09/09 23:49
    • good
    • 0

背理法による証明ですね。


この証明の骨格は、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が1のときはnは素数ではなくなりますよね。(k,l)=(1,3)のときはnは素数になってしまって仮定が成り立たないということでしょうか。(k,l)=(1,1)のときと、k,lが2以上の整数の場合に分けすると、nが素数でない場合が過不足なく表せると思うのですが。

補足日時:2001/09/08 18:51
    • good
    • 0

前の方が答えられているように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は素数には入れない方がいいことがわかりますよね?
    • good
    • 0

1は素数と定義しないからじゃないですか。


定義してしまうと素数は1だけになってしまう。

この回答への補足

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

補足日時:2001/09/08 18:47
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qnを自然数とするとき、n^5/5+n^4/2+n^3/3-n/30が自然数であることを証明せよ。

高校数学の教科書の数列のところの一番最後の一番難しい章末問題で
nを自然数とするとき、n^5/5+n^4/2+n^3/3-n/30が自然数であることを証明せよ。
って問題なんですが、とりあえず数学的帰納法で解くんだろうけど全然解けそうにないです。
月曜日までにやってこないとやばいので、だれか助けてください!!

Aベストアンサー

因数分解すると
n(n+1)(2n+1)(3n^2+3n-1)/30
=n(n+1)(2n+1){3n(n+1)-1}/30
n、n+1のどちらかは必ず2の倍数

n,n+1のどちらも3の倍数でないのは
n=3k+1のときで(kは整数)
2n+1=6k+2+1=6k+3=3(2k+1)
なので、このとき、(2n+1)は3の倍数。
結局、n(n+1)(2n+1)は6の倍数になる。
また、
n=5k+m(kは整数、m=0,1,2,3,4)
とおけば
3n(n+1)-1=15k(5k+2m+1)+3m^2+3m-1
m=0のとき
n=5k
m=1のとき
3n(n+1)-1=15k(5k+3)+5
m=2のとき
2n+1=10n+4+1=5(2n+2)
m=3のとき
3n(n+1)-1=15k(5k+7)+35
m=4のとき
n+1=5k+4+1=5(k+1)
となり、必ず5の因数を含む。
したがって、
n(n+1)(2n+1){3n(n+1)-1}
は30の倍数となる。

QΣ[k=1..∞](-1)^(k+1)/k^2=π^2/12において,|π^2/12-s(n)|<10^-4となる為のnの大きさは?

皆様、宜しくお願い致します。下記の問題でたいそう難儀しております。

[問]与えられたΣ[k=1..∞](-1)^(k+1)/k^2=π^2/12において,|π^2/12-s(n)|<10^-4
となる為にはどのくらい大きい自然数nが選ばれねばならないか決定せよ。
但し,s(n)はこの級数のn項迄の部分和を表す。

という問題なのですがこれはどのようにして解けばいいのでしょうか?

Aベストアンサー

全部答えるとルール違反なので方針だけ。

Σ[k=n+1..∞](-1)^(k+1)/k^2

の絶対値が 10^(-4) よりも小さくなる条件を求めればよい。

Qx^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2

x^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2+・・・+y^n-1)
となるのはなぜですか?
教えてください。

Aベストアンサー

1+r+r^2+・・・+r^(n-1)=(1-r^n)/(1-r)

r=x/yとおくと

1+(x/y)+(x/y)^2+・・・+(x/y)^(n-1)={1-(x/y)^n}/{1-(x/y)}
故に、
{1-(x/y)^n}={1-(x/y)}{1+(x/y)+(x/y)^2+・・・+(x/y)^(n-1)}

両辺にy^nを乗じて
x^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2+・・・+y^n-1)

Qmを自然数,nを奇数とするとき,2(1^n+2^n+…+m^n)がm(m+1)で割り切れる

mを自然数,nを奇数とするとき,2(1^n+2^n+…+m^n)が m(m+1)で割り切れることを証明したいのですが、あることに気づく必要があるといわれたのですが、それがどうもよくわかりません。

また、nが偶数のときには、何か別の性質があるのでしょうか?

Aベストアンサー

自然数をmで割った余りで分類する(剰余類)方法が分かっていればさほど難しい問題ではないですね

mが奇数なら自然数nはkを自然数として
n=mk,mk±1,mk±2,…,mk±(m-1)/2
mが偶数なら
n=mk,mk±1,mk±2,…,mk±(m-2)/2,mk+m/2
と表現できることに注意しましょう。


剰余で分類する問題だと、例えば

3で割り切れる数、3で割って1余る数、3で割って2余る数

のように分けることが多い気がしますが、3で割って2余る数を
3k+2=3(k+1)-1 (k=0,1,2,…)
と見れば
3k-1 (k=1,2,3,…)
と表現してもいいな、と分かりますね。
こう見るとnが奇数に限定されている理由も見えてくると思います。

余裕があったら、合同式などについても調べてみるといいかと思います。

QF_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} の因数分解

F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} 
(n=1,2,3,4,5)
を因数分解せよ、という問題なのですが、どすればよいのでしょうか?

なお、答えは、

F_1=3(b+c)(c+a)(a+b)
F_2=5(b+c)(c+a)(a+b)(Σa^2+Σab)
F_3=7(b+c)(c+a)(a+b)(Σa^4+2Σa^3 b+3Σa^2 b^2+5Σa^2 bc)
F_4=3(b+c)(c+a)(a+b)(3Σa^6+9Σa^5 b+19Σa^4 b^2+35Σa^4 bc+23Σa^3 b^3+63Σa^3 b^2 c)
F_5=11(b+c)(c+a)(a+b)(Σa^8+4Σa^7 b+11Σa^6 b^2+21Σa^6 bc+9Σa^5 b^3+54Σa^5 b^2 c+23Σa^4 b^4+84Σa^4 b^3 c+123Σa^4 b^2 c^2+159Σa^3 b^3 c^2)

のようなのですが、(b+c)(c+a)(a+b)を因数に持つことは分かりますが、残りの因数はどうやってもとめるのでしょうか?

一文字を変数と見て、地道に割り算するしかないのでしょうか?
効率的な計算方法はありますでしょうか?

F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} 
(n=1,2,3,4,5)
を因数分解せよ、という問題なのですが、どすればよいのでしょうか?

なお、答えは、

F_1=3(b+c)(c+a)(a+b)
F_2=5(b+c)(c+a)(a+b)(Σa^2+Σab)
F_3=7(b+c)(c+a)(a+b)(Σa^4+2Σa^3 b+3Σa^2 b^2+5Σa^2 bc)
F_4=3(b+c)(c+a)(a+b)(3Σa^6+9Σa^5 b+19Σa^4 b^2+35Σa^4 bc+23Σa^3 b^3+63Σa^3 b^2 c)
F_5=11(b+c)(c+a)(a+b)(Σa^8+4Σa^7 b+11Σa^6 b^2+21Σa^6 bc+9Σa^5 b^3+54Σa^5 b^2 c+23Σa^4 b^4+84Σa^4 b^3 c+123Σa^4 b^2 c^2+159Σa^3 b^3 c^...続きを読む

Aベストアンサー

最後までは計算していませんが、次の方法でできそうです。
F_n = (b+c)(c+a)(a+b)(Σ[ABC] k_ABC a^A b^B c^C) とおきます。
(ここで、A+B+C = 2n+1 です。)
展開すると、F_n = (a^2 b + 略 + 2abc)(Σ[ABC] k_ABC a^A b^B c^C) です。
そして、F_n を例えば、a で A+2 回偏微分、a で B+1 回偏微分、
a で C 回偏微分、した後、a,b,c に 0 を代入します。
F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} に対しても同じようにします。
このようにすると、例えば C > 0 であれば、
k_ABC (A+2)!(B+1)!(C)! = (2n+1)! となり、係数が得られます。


人気Q&Aランキング

おすすめ情報