12110002

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である必要がある。 これ以上、わかりません＞？＜・・・

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