yahoo知恵袋にて

MC-such さん

  • 公開日時: 2010/12/06 22:50
  • 閲覧数: 5315
  • コメント数: 7
  • カテゴリ: 研究・考察

こんな質問がありました。学校の課題とのことです。

 

2^17-1=131071
が素数であることはどうやって示せますか?

 

これに対して、こんな解答をした人がいました。

 

2^17-1を因数分解すると(2^(17/2)-1)(2^(17/2)+1)
ですが、2^(17/2)-1=256√2-1、2^(17/2)+1=256√2+1は
どちらも整数ではありません。
よって2^17-1は自身と1以外では割り切れないので素数です。

ちなみに、nを正の整数として
2^n-1=(2^(n/2)-1)(2^(n/2)+1)とした場合、
nが偶数であれば2^n-1は素数ではなく、奇数ならば素数であることが分かります。

 

 

 

で、この解答、ベストアンサーに選ばれてました。

これ完全に間違いですよね? 別の人で「2^15-1は合成数」だと指摘した人がいて、私も2^67-1は合成数だったと記憶しています。

 

もう知恵袋のほうにはこのことについてこれ以上コメントできません。

なので、どなたか「コンピュータで計算する」以外の解答をご存知でしたらコメお願いしますm(_ _)m

公序良俗に反する不適切な投稿を発見された方はこちらよりご報告ください

この投稿にフォローする

コメントをつけるにはログインが必要です。

最新10件表示

No メッセージ 投稿者 日時    
1
[式:…] (nが奇数)のとき、[式:…]は素数とは限りません。
 例 [式:…]
すなわち[式:…]を利用。[式:…]
質問の意図と違っていたらごめんなさい。
クロニャンコ さん 2010/12/06 23:47:18 報告
2
≫これ完全に間違いですよね?

はい、完全に間違いです。論評するのも気が引けるくらい。

ちなみに [式:…] が素数であるためには [式:…] が素数であることが必要条件ですが、十分条件ではありません。最小の反例は:
   [式:…]
上を裏返すと [式:…] が合成数なら [式:…] は無条件で合成数です。
ここらについては「メルセンヌ素数」で検索してみてください。

≫なので、どなたか「コンピュータで計算する」以外の解答をご存知でしたらコメお願いします

本質的にうまい方法があるわけではありません。
  [式:…]
なので、362 以下の素数で地道に割ってみるのが基本でしょう(これぐらいなら手計算でも大したことはない)。一方、
  「[式:…][式:…] の素因数なら、[式:…][式:…] は正整数)と表せる」
といった定理があり、それで調べる範囲を絞り込めますが、それを証明するのは高校レベルでは難しいでしょう。
  参考:上の反例では、[式:…]
  この定理を使えば、[式:…] について実際に割ってみる必要のある素数は:
     [式:…]
  の4個に絞られます。
より一般にはルーカステスト(リュカテスト)のような判定方法もありますが、今の場合はかえって面倒です。
平賀 譲 さん 2010/12/06 23:52:14 報告
3 近谷 邦彦 さん 2010/12/07 10:05:52 報告
4
ちなみに本問とは直接関係ないですが
[式:…]が素数ならば
[式:…]は完全数になります。
33846 さん 2010/12/07 11:20:44 報告
5
皆さんコメありがとうございます。とても参考になりました。


自然数を無理数に因数分解するというぶっとんだ発想にもやもやしていたのがやっとすっきりできました(^^)



>kunnyさん
見てみましたが、これ基本的な証明なんですか……
MC-such さん 2010/12/07 22:04:07 報告
6
>これ基本的な証明なんですか
この掲示板に何度か書いているのですが,大学の数学と高校の数学が大きく違うのは当然のこととして,大学入試レベルの数学と,海外のコンテスト系の数学も大きく違います.
この示してあるサイトのレベルは何を想定しているのか知りませんが,整数論に関しては,大学の整数論の知識が前提でしょう.IMOでもルジャンドルの記号は前提ではありません(生徒が使うことはあるでしょうが).
日本の通常の学習だけをしている段階では,ルジャンドルの記号からしてわからないと思います.サイトに書かれたものをそのまま独力で理解されたいなら,大学の整数論の本を一冊買われて,拾い読みくらいはされてからにしたほうがよいと思います.
安田 亨 さん 2010/12/08 11:47:43 報告
7
もし,いま受験真っ只中の高校生だとしたら
整数論の本は,以外と新しい言葉・式が多く
理解しがたい(微積や線形代数に比べると)ので。

昔,初学のころ,a|b はどちらがどちらで割り切れるのか?
ということをよく忘れるので机に書いていました。

受験が終わってからにした方が賢明かも。
『平方剰余の相互法則』とか
言葉の理解だけでも・・・時間が無限にあればいいですね。
33846 さん 2010/12/08 16:10:25 報告