12110002


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

NO.2-1 素数判定 ~難易度 ?

問題

 38 :以下、名無しにかわりましてVIPがお送りします:2008/10/29(水) 22:23:51.31 ID:GIEa1KdF0
   問題
   2^2017-1は素数か合成数か? 

解答

+...

合成数である。

解説(不完全)

2^n≡1(mod p)となるpを探す。(p≧3の素数) ここで、2^nのnを大きくしていってpで割った余りが1となった時に余りが循環することを示す。 n=1の時の余りは、2である。 2^n=ap+1の時、2^(n+1)=2ap+2より、余りは2となって余りが1になった時に余りが循環する。 ここで、2017は素数より 余りの循環が2017である素数を探せばいい。 これには、p≧2017である必要がある。 これ以上、わかりません>?<・・・

  • 補足
    • メルセンヌ素数に含まれてないので合成数であることは明らかです。
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。