■リュカ数の問題(その8)

リュカテストはS2=4から始まる漸化式

Sn=(Sn-1)^2-2

S2=4,S3=14,S4=194,S5=37634,・・・

において

SpがMp=2^p-1で割り切れるとき、かつ、そのときに限り、Mpは素数であるというものである。

たとえば、M11=2^11-1=2047=23・89、S11はM11で割り切れない→M11は合成数。 レーマーはP=521,607はメルセンヌ素数であることを証明した。

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

【1】メルセンヌ数の因数

リュカテストはどんな因数をも示さないが、p=4k+3型Mpに対しては

もしMpが合成数ならば、それが(p-1)/2で割り切れないとき、かつ、そのときに限り、Mpは2p+1で割り切れる。

たとえば、p=11=4k+3型、M11=2047は(11-1)/2=5で割り切れない→2p+1=23で割り切れる

p=23=4k+3型、M23=38388607は(23-1)/2=11で割り切れない→2p+1=47で割り切れる

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