解決済み

メルセンヌ数について

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

お礼率 14% (22/147)

正の整数kについて、Mk = 2^k - 1がメルセンヌ数である。
pは2ではない素数で、qはMpを割り切る事の出来る素数である。
この時、

1)どうすれば2^(q-1) - 1がqで割り切れると示せるのでしょうか?
2)gcd(2^(q-1), 2^p - 1) = 2^(gcd(q-1,p)) - 1は正しいとすると、gcd(q-1, p) = pである事はどうすれば示せるのでしょうか?
3)q = mp+1である事を偶数mで正しい事はどうすれば示せるのでしょうか?
4)Mpを割る事の出来るdはd ≡ 1(mod 2p)を満たす事はどうすれば示せるでしょうか?

メルセンヌ数の性質なんですが、どなたかご教授お願いします。。。

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

  • 回答No.3

ベストアンサー率 59% (355/599)

(4)だけ
>4)Mpを割る事の出来るdはd ≡ 1(mod 2p)を満たす

d=(q1^r1)*(q2^r2)*(q3^r3)・・・と素因数分解する(q1,q2,q3・・・は素数)。
3)の性質より,q1=2m1*p+1,q2=2m2*p+1,q3=2m3*p+1・・・とおける。
ここでq1^r1=(2*m1*p+1)^r1≡1^r1=1(mod 2p)
同様にq2^r2≡1(mod 2p),q3^r3≡1(mod 2p)・・・
よってd≡1(mod 2p)
感謝経済

その他の回答 (全2件)

  • 回答No.2

ベストアンサー率 59% (355/599)

(3)だけ
>正の整数kについて、Mk = 2^k - 1がメルセンヌ数である。
>pは2ではない素数で、qはMpを割り切る事の出来る素数である。
>3)q = mp+1である事を偶数mで正しい事はどうすれば示せるのでしょうか?

mod qの剰余系の上で乗法群における元2の位数をkとする。
すなわち,2^1,2^2,2^3,・・・,2^kのうち,2^k≡1(mod q)を満たす最小の自然数をkとする。

ここで,2^x≡1(mod q)なら,xはkの倍数である。
(∵xをkで割った余りをrすると,2^r≡1となる。r≠0だと「kが最小の自然数」に反する)

一方,qはMp=(2^p)-1を割り切る素数なので,2^p≡1(mod q)である。
よってpはkの倍数。pが素数なのでk=pでなければならない。

さて,(1)から2^(q-1)≡1(mod q)なので,q-1はpの倍数である。すなわち
q-1=mpと書ける。
ここで,qは2ではない素数なので,q-1は偶数。また,pは2ではない素数ゆえ奇数。
よってmは偶数に限られる。
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

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

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

特集


感謝指数によるOK-チップ配布スタート!

ピックアップ

ページ先頭へ