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

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

M3=2^3-1＝7→S3=14は7で割り切れる→7はメルセンヌ素数

M5=2^5-1＝31→S5=37634は31で割り切れる→31はメルセンヌ素数

M7=2^7-1=127→？

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

Sn=(Sn-1)^2-2

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

S2=4,S3=14　　(mod127),

S4=194=67　　(mod127)

S5=37634=67^2-2=4487=42　　(mod127)

S6=42^2-2=1762=111　　(mod127)

S7=111^2-2=12319=0　　(mod127)

M7=2^7-1=127→S7は127で割り切れる→127はメルセンヌ素数

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

M11＝2^11-1＝2047＝23・89→？

Sn=(Sn-1)^2-2

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

S2=4,S3=14　　(mod2047),

S4=194　　(mod2047)

S5=37634=788　　(mod2047)

S6=788^2-2＝620942=701　　(mod2047)

S7=701^2-2=491399=119　　(mod2047)

S8=119^2-2＝14159=1877　　(mod2047)

S9=1877^2-2=3523127=240　　(mod2047)

S10=240^2-2=57598=282　　(mod2047)

S11=282^2-2=79522=1736　　(mod2047)

M11＝2^11-1＝2047＝23・89→？→S11は2047で割り切れない→2047はメルセンヌ素数ではない

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

リュカ・レーマーの判定法の証明はペル方程式x^2-3y^2=1の解を用いる意外なものになっている。

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