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

このQ&Aに関連する最新のQ&A

A 回答 (5件)

そういう数のことを、


「2を底とする(フェルマーテストの意味での)擬素数」
といいます。つまり、フェルマーテストを通ってしまう合成数ですね。
1000以下だと、341, 561, 645の3つです。
http://www.google.com/search?hl=ja&lr=lang_ja&ie …
    • good
    • 0

ちょっと詳しく書いてあるページを見つけました。


http://mathworld.wolfram.com/PouletNumber.html

また、そこからたどれる
http://www.research.att.com/~njas/sequences/A001 …
にこういう数のリストが載っているんですが、
その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.
ていう、生成のための鋳型みたいな方法が書いてありますね。
ただし、全てを求めることは不可能みたいですが。
    • good
    • 0

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が素数でないかどうかを調べる必要があるのが面倒なところです。
    • good
    • 0

ANo.1ですが、


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

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が求まります。

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報