素数の問題です。「次のことを示せ。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のときも考えないといけないと思うのですが。
よろしくお願いします。
No.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は素数である。」
まあ、対偶での証明とほとんど同じですが。
細かいことでも自分の納得するまで考える姿勢は素晴らしいと思います。
文章だとどうしても細かいニュアンスが伝えられなくて
分かりにくいところもあるかもしれません。
もしあれば遠慮なく質問してくださいね。
No.8
- 回答日時:
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の場合は実際に代入して調べてしまおう、
というわけです。
お返事どうもありがとうございます。なるほど、解答に不備があったのですね。
>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は素数である。」という仮定で、解答では、違う視点から、違う仮定を立てて証明するという方法だと思うので、どこと矛盾が起きているのかよくわかりません。もしよろしければ、お返事いただけますでしょうか。お返事どうもありがとうございました。
No.7
- 回答日時:
あ、なるほど。
そういう疑問だったわけですね。「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
- 回答日時:
「~とおく。
」は数学特有の言い回しの問題で難しいですね。結論から言えば、そう置けば証明(または問題が解ける)できるから。
の一言になるのでしょう。(笑)
ただ、某問題集の解答によれば、「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しか属さないと思ったのですが・・・。
どこか私ずれているのでしょうか・・・。
No.5
- 回答日時:
「メルセンヌ素数」とyahooで調べるのだ。
ちなみに○ooはあまり載っていない。不便なことだぜ。ぷんぷん。
ありがとうございました。行って来ました。メルセンヌ素数っていうんですね。人類って知らない間にすごいことやってたんですね。知らない世界だったので、数学の歴史を見て大変興味深かったです。
No.4
- 回答日時:
「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」って素数でない自然数ですよね。もしかして私スゴイ間違いしてますでしょうか(^^.)
No.3
- 回答日時:
背理法による証明ですね。
この証明の骨格は、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が素数でない場合が過不足なく表せると思うのですが。
No.2
- 回答日時:
前の方が答えられているように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は素数には入れない方がいいことがわかりますよね?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 以下 n を自然数, p を素数とする. (a) 整数10000を 10000=(a_4)7^4+( 3 2022/05/19 16:54
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- 数学 【 数A 自然数の積と素因数の個数 】 2 2023/03/02 23:58
- 数学 方程式 √x=-1 の解 2 2022/07/08 17:26
- 数学 2次以上の多項式g(x)であって, 任意の無理数に対して無理数の値を取るものは存在しないことを示せ. 8 2022/06/27 11:28
- 数学 正の約数の個数が20個である最小の自然数を求めよ」 という問題で、(□+1)×(△+1)=20となる 4 2022/07/26 11:58
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- 数学 素数について 7 2022/03/31 02:33
- 大学受験 至急! 数学 整数 なぜ3以上にならないのですか? 3 2023/01/29 12:47
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
a>0、b>0⇔a+b>0、ab>0
-
共分散の符号と相関係数の符号...
-
背理法の必要十分性について
-
n=3の倍数ならば、n=6の倍数で...
-
命題「PならばQ」でPが偽ならば...
-
命題の証明で・・・
-
強い仮定、弱い仮定、とは
-
x≠1⇒xの二乗≠1の真偽
-
天使と悪魔(論理学)
-
nは自然数 n^2と2n+1は互いに素...
-
数A論証の問題がまったくわかり...
-
nが自然数のとき、2^n +1 +3^2...
-
逆、裏、否定、対偶
-
背理法について
-
3.141592653589793238462643383...
-
絶対とはなんなのか
-
素数の問題です
-
「逆もまた真なり」について
-
背理法と対偶証明の違いについて
-
a,bが有理数として√6が無理数を...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「逆もまた真なり」について
-
命題「PならばQ」でPが偽ならば...
-
a>0、b>0⇔a+b>0、ab>0
-
強い仮定、弱い仮定、とは
-
n=3の倍数ならば、n=6の倍数で...
-
「逆は必ずしも真ならず」の証...
-
数学的帰納法の根本的な疑問な...
-
対偶法による無理数の証明につ...
-
数学の背理法について質問です...
-
有理数を文字置き→互いに素な整...
-
写真の命題を数学的帰納法で証...
-
nは自然数 n^2と2n+1は互いに素...
-
a,bが有理数として√6が無理数を...
-
pならばqである の否定について
-
数学の論理学的な質問なんです...
-
【命題が偽である場合の反例の...
-
背理法について質問があります...
-
自然数の証明・・・?
-
青チャートに、「命題p⇒qの否定...
-
数学 12k(2k^2+1)を36の倍数と...
おすすめ情報