■一般化フィボナッチ数(その25)

リュカテストは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の解を用いる意外なものになっている。

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