題目：
若 Rn=21an+bn ，其中 a=3+22b=3−22 ，且 n=0123。試問 R12345 的個位數為何？


解答：

因為 a+b=6 且 ab=1，所以 ab 為 x2−6x+1=0 的兩根，

a2−6a+1=0 且 b2−6b+1=0

an+2−6an+1+an=0 且 bn+2−6bn+1+bn=0n=0123

an+2+bn+2−6an+1+bn+1+an+bn=0n=0123 

21an+2+bn+2−621an+1+bn+1+21an+bn=0n=0123 

Rn+2−6Rn+1+Rn=0n=0123

Rn+2=6Rn+1−Rnn=0123

且由 R0=1R1=3，就可以開始條列，如下

n	0	1	2	3	4	5	6	7
Rn 除以10的餘數	1	3	7	9	7	3	1	3

列到開始有兩位數字跟前面一樣，就可以停止了（因為由遞迴關係式可知，每一項只與前兩項有關，故若前兩項相同，後面的結果亦相同）

由上表可以知道 Rn 除以 10 的餘數每六個數字一循環，而 12345 除以 6 的餘數為 3，

故，R12345 除以 10 的餘數=R3 除以 10 的餘數=9

補上出處，96和美高中
這類題目的遞迴式我都是這樣寫的
21(an+1+bn+1)=(a+b)21(an+bn)−(ab)21(an−1+bn−1)
得到Rn+1=6Rn−Rn−1

[ 本帖最後由 bugmens 於 2009-6-25 06:42 AM 編輯 ]

想請教我的做法哪裡錯了?感謝~
a3+b3=198a3b3=1
2Rn=(a3)n+(b3)n
2R1=a3+b3=198
2R2=a6+b6=1982−2==2
2R3=a9+b9==1982−1198==8
soR為2循環:4141所求為n=4115時所以答案為4

[ 本帖最後由 idontnow90 於 2013-6-3 12:00 AM 編輯 ]

遞迴關係式可知，每一項只與前兩項有關，故若前兩項相同，後面的結果才會相同

因此不能只看一項出現，必須要看連續兩個出現與前面重複，才可以保證重複。



另外， 2某數8(mod10)，並不保證 某數4(mod10)

例如：298(mod10)，但是 「9 並不同餘 4(mod10)」

這是因為 2 與 10 並不互質，因此在 (mod10) 的剩餘系統中，並不存在 2(mod10) 的乘法反元素，

即「不存在整數 a，使得 a21(mod10)」，

因此無法在左右都是偶數的同餘式中～以左右同乘 a(mod10) 來消掉 2(mod10)。

另解：

因為 3223=99702 



所以 213+2212345+3−2212345 

　　　=2199+7024115+99−7024115 

　　　　（將上式以二項式定理展開後合併，偶數項都會對消掉，
　　　　　奇數項都會有兩倍與最外面的 21 相消，
　　　　　消掉兩倍之後的奇數項～除第一項以外～其餘都是 10 的倍數，）

　　　994115(mod10)

　　　−14115(mod10) 

　　　−1(mod10)

　　　9(mod10)

那這樣想再請教一下我下面這兩題這樣做會對..純粹是巧合嗎??謝謝

請教這個會對也是巧合嗎?
便利貼上寫得是這個做法..白紙上寫得是原本的做法

[ 本帖最後由 idontnow90 於 2013-6-3 09:37 PM 編輯 ]

這樣寫會對沒錯呀，

但是最好多檢查到餘數是 080208

發現有兩數字 08 開始重複了，

就可以確定餘數是以 0802 的方式循環。

否則你可以想看何以判斷餘數是「四個」一循還？還是「兩個」一循環？還是「三個」一循環？還是「多少個」一循環呢？

由 an=10an−1−an−2 可以知道要檢查到有兩個連續的餘數開始重複出現，才能確定開始循環了。

或是再加上簡單說明 an=10an−1−an−2an−an−2(mod10)an−an−2an−4(mod10)

因此，可知 an(mod10) 會四個一循環。

引用:

原帖由 weiye 於 2013-6-3 09:50 PM 發表

發現有兩數字 08 開始重複了，

就可以確定餘數是以 0802 的方式循環。

.

那這樣我有點搞混了ㄟ..
如果說剛剛那題目(我們先撇開那個2倍的錯誤不看..)
是Sn=(a3)n+(b3)nS1=8S2=2  S3=8S4=2他也是連續兩數字 82 重複

但是現在這題an=(p2)n+(q2)na1=0a2=8a3=0a4=2他也是連續兩數字 08 重複

為什麼一題會對一題會錯??他們得遞迴式都是跟前兩項有關阿??

抱歉..搞不太清楚.還請賜教.感謝~

你後來手寫回覆的這一題不是連續兩個數字 08 重複呀，

你看看你手寫的內容，明明就是 0802 連續四個數字的重複呀。

還有你第一次回文的 2Rn(mod10) 是兩個數字重複沒錯，但是 Rn(mod10) 並不見得就會是兩個數字重複呀！

（2Rn(mod10) 我只是點出你並沒有充分的檢查～並不是說循環長度有誤！）