■素数であるか? (その24)

[1]メルセンヌ数2^p−1の素因数をpで割ると1余る素数になる.

さらに

[2]pが4で割って3余り,2p+1が素数(ソフィー・ジェルマン素数)ならば,2^p−1は2p+1で割り切れる.

 素因数を見つけることなく,直接メルセンヌ素数の判定法がリュカ・レーマーの判定法「数列SnをS1=4,Sn+1=Sn^2−2で定める.pが奇数の素数のとき,2^p−1が素数であるための必要十分条件はSp-1が2^p−1で割り切れること」である.

===================================

【1】リュカ・レーマーの判定法と2重指数型公式

  gn+1=(gn)^2−2,g0=4

は,メルセンス数の素数性判定のために用いられる数列である(リュカ・レーマーの判定法).

  gn+1=(gn)^2−2,g0=m

とする.

 2重指数型公式

  gn=ω1^(2^n)+ω2^(2^n)

のω1,ω2は掛けて1,足してmとなる必要があることから,

  ω1=m/2+√c

  ω2=m/2−√c

  m^2/4−c=1→c=m^2/4−1

  (m,c)=(4,3),(6,8),(8,15),・・・

===================================

  gn+1=(gn)^2+2,g0=m

の場合,掛けて−1であっても,

  2(ω1ω1)^(2^n)+2≠0

なので

  ω1=m/2+√c

  ω2=m/2−√c

  m^2/4−c=−1→c=m^2/4+1はNGである.

===================================