■ドミノ被覆・畳被覆(その43)

pが素数ならば

Lp=1 (mod p)

が成り立つ。しかし、この逆

Ln=1 (mod n)ならばnは素数であるは正しくない(フィボナッチ擬素数)。

たとえば、

 L705=1 (mod 705)

であるが、705=3・5・47

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

A=[0,1]

[1,1]とすると,|A^n|=(-1)^n

[Ln ]=[0,1][L0]

[Ln+1] [1,1][L1]

[L704]=A^704][2]

[L705] [1]

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

[L704]=A^704][2] (mod 705)

[L705] [1]

を評価したいのであるが、

704=2^6+2^7+2^9

A^2^6=[142,423] (mod705)

=[423,565]

A^2^7=[283,141] (mod705)

=[141,424]

A^2^9=[424,564] (mod705)

=[564,283]

これらを掛け合わせると

A^704=[142,423] (mod705)

=[423,565]

したがって、

[L704]=A^704][2]=[ 707]={2} (mod 705)

[L705] [1] {1411] [1]

より、

 L705=L1=1 (mod 705)

 L704=L0=2 (mod 705)

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

L706=L705+L704=L1+L0=L2=3 (mod 705)

L707=L706+L705=L2+L1=L3=4 (mod 705)

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