12110005

NO.5-1　メルセンヌ素数 ～難易度☆☆★★★

問題(改題)

 108 ：以下、名無しにかわりましてVIPがお送りします：2008/11/17(月) 21:10:58.16 ID:m5YHj5290
   問題
   m^n-1は素数である。
   (1)mの値を求めよ。
   (2)nは素数であることを証明せよ。

• 補足
  • m,nは自然数
  • n≧2

解答

...

(1)m=2 (2)解説参照

解説

(1)

m^n-1=(m-1)(m^(n-1)+…+1)と因数分解されることから

m-1≧2の時、素数という条件に反するため、m-1=1。

∴m=2。

(2)

nを合成数と仮定し、n=abとし、2^a=pとでもおく。(a,b≧2)

p^b-1=(p-1)(p^(b-1)+…+1)=(2^a-1)(2^a(b-1)+2^a(b-2)+…+1)

a,b≧2より、2^a-1≧2となるため素数の条件に反する。

これより、nは素数。

参考

• メルセンヌ素数>