ここから本文です

メルセンヌ数について

プロフィール画像

阿良々木　FOXの弟さん

2012/3/500:54:40

メルセンヌ数について

正の整数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)を満たす事はどうすれば示せるでしょうか？

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

閲覧数：
396
回答数：
1

違反報告

ベストアンサーに選ばれた回答

プロフィール画像

fermatprime65537さん

編集あり2012/3/502:04:01

1)
qはMp＝2^p－1を割り切る素数だから奇数なので、2はqで割り切れません。
したがって、フェルマーの小定理により
2^(q－1)≡1 (mod q)

したがって、2^(q－1)－1はqで割り切れます。


2)
gcd(q－1, p)はpの約数で、pは素数だから
gcd(q－1, p)＝1またはp
ここで、gcd(q－1, p)＝1と仮定すると
gcd(2^(q-1)－1, 2^p－1)＝2^1－1＝1
すなわち、2^(q-1)－1と2^p－1は互いに素です。
しかし、1)により2^(q-1)－1はqで割り切れ、さらに2^p－1はqで割り切れるから、qがこれらの公約数なので、矛盾します。
したがって、gcd(q－1, p)＝pです。


3)
2)により、gcd(q－1, p)＝pだから、q－1はpで割り切れます。
すなわち、q－1＝mp（mは整数）と表わされます。
そして、q－1は偶数でpは奇数だから、mは偶数です。

したがって、q＝mp＋1（mは偶数）と表わされます。


4)
dをMpを割り切る任意の整数とします。

まず、d＝1の場合は
d≡1 (mod 2p)となるのは明らかです。

次に、d＞1の場合は
dを素因数分解すると
d＝q1*...*qr（rは正の整数で、q1, ..., qrは素数）と表わされます。
ここで、qi（1≦i≦r）はdの約数だからMpを割り切れる素数なので、3)により
qi＝mip＋1（miは偶数）と表わされます。
すなわち
qi≡1 (mod 2p)
したがって
d＝q1*...*qr≡1*...*1＝1 (mod 2p)

以上から、Mpを割り切ることのできる任意の整数dは、d≡1 (mod 2p)を満たします。

----------
分かりにくいところなどがありましたら、補足等でご指摘ください。

違反報告

プロフィール画像

質問した人からのコメント

2012/3/5 02:14:18

降参 ありがとうございました

あわせて知りたい

この質問につけられたタグ

みんなで作る知恵袋　悩みや疑問、なんでも気軽にきいちゃおう！

Q&Aをキーワードで検索：

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる