［１］リュカ（１８７２年）

ｐを素数，０≦ｑ＜ｐ，０≦ｒ＜ｐとする．

（ｐｎ＋ｑ，ｐｋ＋ｒ）＝（ｎ，ｋ）（ｑ，ｒ）　ｍｏｄ　ｐ

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

ｐ進数でn=(nr,nr-1,・・・,n1,n0)p,k=(kr,kr-1,・・・,k1,k0)pとすると

（ｎ，ｋ）=(nr,kr)(nr-1,kr-1)・・・(n1,k1)(n0,k0) modp

(34241,17101) mod3は?　

34241=(1120212002)3,17101=(0212110101)3

(34241,17101) mod3=(1,0)(1,2)(2,1)(0,2)(2,1)(1,1)(2,0)(0,1)(0,0)(2,1)=1・0・2・0・2・1・1・0・1・2=0 (mod3)

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

(34241,17101) mod5は?　

34241=(1444431)5,17101=(1021401)5

(34241,17101) mod5=(1,1)(4,0)(4,2)(4,1)(4,4)(3,0)(1,1)=1・1・6・4・1=24=4 (mod5)

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