リュカテストは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はメルセンヌ素数であることを証明した。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

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

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

たとえば、p=11=4k+3型、Ｍ11=2047は（11-1）/2＝5で割り切れない→2ｐ+1＝23で割り切れる

p=23=4k+3型、Ｍ23＝38388607は（23-1）/2＝11で割り切れない→2ｐ+1＝47で割り切れる

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝