解き方を教えてください

質問

「ｎが素数でない奇数で2^(n-1)-1がｎで割り切れる数を求めよ」といゆう問題が学校ででたのですが、全く解き方がわかりません。
解き方を教えてください。よろしくお願いします。

回答No.2

rabbit_cat · ベストアンサー

そういう数のことを、
「２を底とする（フェルマーテストの意味での）擬素数」
といいます。つまり、フェルマーテストを通ってしまう合成数ですね。
1000以下だと、341, 561, 645の３つです。
http://www.google.com/search?hl=ja&lr=lang_ja&ie=UTF-8&oe=UTF-8&q=%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%83%86%E3%82%B9%E3%83%88&num=50

回答No.5

rabbit_cat

ちょっと詳しく書いてあるページを見つけました。
http://mathworld.wolfram.com/PouletNumber.html

また、そこからたどれる
http://www.research.att.com/~njas/sequences/A001567
にこういう数のリストが載っているんですが、
そのTheoryのところを見ると、
If both numbers q and 2q-1 are primes (q is in the sequence A005382) and n=q*(2q-1) then 2^(n-1)==1 (mod n) (n is in the sequence) iff q is of the form 12k+1.
ていう、生成のための鋳型みたいな方法が書いてありますね。
ただし、全てを求めることは不可能みたいですが。

回答No.4

R_Earl

ANo.1、ANo.3です。
ANo.3では間違っていたと書きましたが、
良く考えてみると、ANo.1の方法でも
「2^(n-1)-1を割り切れる、素数でない奇数n」
を求めることはできるようです
(その代わり、該当するnを『全て』求めることは不可能です)。

ANo.1で書き忘れましたが、
nは「二進数表記すると111…1となる数」に限定して考えています。
例えば十進数111111111111は「十進数の11」、「十進数の111」、
「十進数の1111」、「十進数の111111」で割りきれます。
同様に二進数111111111111も「二進数の11(十進数の3)」、「二進数の111」、
「二進数の1111」、「二進数の111111」で
割りきれます。
この性質を利用したのがANo.1で紹介した方法です。

この方法で一番初めに見つかるのはn = 2047です(約10回の試行で見つかります)。
10回ぐらいなら手計算でも何とかなりますが、
2047が素数でないかどうかを調べる必要があるのが面倒なところです。

回答No.3

R_Earl

ANo.1ですが、
私が書いた方法は間違っていました。
なのでANo.1の回答は無視してください。

回答No.1

R_Earl

n = 1がまず該当しますね。

その他のnの求め方として、次のような方法を思いつきました。
2^(n-1) - 1を2進数表記すると、
1111111111111111111…1
と1だけが続く数になります。
なので「2^(n-1) - 1を2進数表記した時の1の数」と、
「nを2進数表記した時の1の数」を考えれば
2^(n-1) - 1を割りきれるnが求まります。

もっとスマートな方法があるかもしれません。