Board logo

標題: 整數論的題目，同餘的題目. [打印本頁]
作者: weiye    時間: 2009-6-24 21:41     標題: 整數論的題目，同餘的題目.

題目：
若 \(\displaystyle R_n=\frac{1}{2}\left(a^n+b^n\right)\)，其中 \(\displaystyle a=3+2\sqrt{2}, b=3-2\sqrt{2}\)，且 \(n=0,1,2,3,\cdots\)。試問 \(R_{12345}\) 的個位數為何？


解答：

因為 \(a+b=6\) 且 \(ab=1\)，所以 \(a,b\) 為 \(x^2-6x+1=0\) 的兩根，

\(\displaystyle \Rightarrow a^2-6a+1=0\) 且 \(b^2-6b+1=0\)

\(\displaystyle \Rightarrow a^{n+2}-6a^{n+1}+a^n=0\mbox{ 且 } b^{n+2}-6b^{n+1}+b^n=0\;\forall n=0,1,2,3\cdots\)

\(\displaystyle \Rightarrow \left(a^{n+2}+b^{n+2}\right)-6\left(a^{n+1}+b^{n+1}\right)+\left(a^n+b^n\right)=0\;\forall n=0,1,2,3\cdots\)

\(\displaystyle \Rightarrow\frac{1}{2}\left(a^{n+2}+b^{n+2}\right)-6\times\frac{1}{2}\left(a^{n+1}+b^{n+1}\right)+\frac{1}{2}\left(a^n+b^n\right)=0\;\forall n=0,1,2,3\cdots\)

\(\displaystyle \Rightarrow R_{n+2}-6R_{n+1}+R_{n}=0\;\forall n=0,1,2,3\cdots\)

\(\displaystyle \Rightarrow R_{n+2}=6R_{n+1}-R_{n}\;\forall n=0,1,2,3\cdots\)

且由 \(R_0=1,\; R_1=3\)，就可以開始條列，如下

\(n\) 01
2
3
4
5
6
7
\(R_n\) 除以\(10\)的餘數
1
3
7
9
7
3
1
3

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

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

故，\(R_{12345}\) 除以 \(10\) 的餘數\(=R_3\) 除以 \(10\) 的餘數\(=9.\)
作者: bugmens    時間: 2009-6-25 06:39

補上出處，96和美高中
這類題目的遞迴式我都是這樣寫的
\( \frac{1}{2}(a^{n+1}+b^{n+1})=(a+b)\frac{1}{2}(a^n+b^n)-(ab)\frac{1}{2}(a^{n-1}+b^{n-1}) \)
得到\( R_{n+1}=6R_n-R_{n-1} \)

[ 本帖最後由 bugmens 於 2009-6-25 06:42 AM 編輯 ]
作者: idontnow90    時間: 2013-6-2 23:59

想請教我的做法哪裡錯了?感謝~
\( a^3+b^3=198, a^3*b^3=1,\)
\(2R_n=(a^3)^n+(b^3)^n\)
\(2R_1=a^3+b^3=198\)
\(2R_2=a^6+b^6=198^2-2==>2\)
\(2R_3=a^9+b^9==>198*2-1*198==>8\)
\(so, R為2循環:4,1,4,1,...
所求為n=4115時,所以答案為4\)

[ 本帖最後由 idontnow90 於 2013-6-3 12:00 AM 編輯 ]
作者: weiye    時間: 2013-6-3 00:24     標題: 回復 3# idontnow90 的帖子

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

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



另外， \(2\times\mbox{某數}\equiv 8\pmod{10}\)，並不保證 \(\mbox{某數}\equiv4\pmod{10}\)

例如：\(2\times9\equiv8\pmod{10}\)，但是 「\(9\) 並不同餘 \(4\pmod{10}\)」

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

即「不存在整數 \(a\)，使得 \(a\times 2\equiv1\pmod{10}\)」，

因此無法在左右都是偶數的同餘式中～以左右同乘 \(a\pmod{10}\) 來消掉 \(2\pmod{10}\)。
作者: weiye    時間: 2013-6-3 08:17     標題: 回復 1# weiye 的帖子

另解：

因為 \(\left(3\pm2\sqrt{2}\right)^3=99\pm70\sqrt{2}\)



所以 \(\displaystyle\frac{1}{2}\left(\left(3+2\sqrt{2}\right)^{12345}+\left(3-2\sqrt{2}\right)^{12345}\right)\)

　　　\(\displaystyle=\frac{1}{2}\left(\left(99+70\sqrt{2}\right)^{4115}+\left(99-70\sqrt{2}\right)^{4115}\right)\)

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

　　　\(\equiv 99^{4115}\pmod{10}\)

　　　\(\equiv\left(-1\right)^{4115}\pmod{10}\)

　　　\(\equiv-1\pmod{10}\)

　　　\(\equiv9\pmod{10}\)
作者: idontnow90    時間: 2013-6-3 21:08

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

圖片附件: IMG_7614.jpg (2013-6-3 21:47, 251.98 KB) / 該附件被下載次數 6582
https://math.pro/db/attachment.php?aid=1748&k=fac5c22212fe239bf6ca51388c070146&t=1732279025

作者: idontnow90    時間: 2013-6-3 21:35

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

[ 本帖最後由 idontnow90 於 2013-6-3 09:37 PM 編輯 ]
作者: weiye    時間: 2013-6-3 21:50     標題: 回復 7# idontnow90 的帖子

這樣寫會對沒錯呀，

但是最好多檢查到餘數是 \(0,8,0,2,0,8\)

發現有兩數字 \(0,8\) 開始重複了，

就可以確定餘數是以 \(0,8,0,2\) 的方式循環。

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

由 \(a_n=10a_{n-1}-a_{n-2}\) 可以知道要檢查到有兩個連續的餘數開始重複出現，才能確定開始循環了。

或是再加上簡單說明 \(a_n=10a_{n-1}-a_{n-2}\Rightarrow a_{n}\equiv-a_{n-2}\pmod{10}\Rightarrow a_{n}\equiv-a_{n-2}\equiv a_{n-4}\pmod{10}\)

因此，可知 \(a_n\pmod{10}\) 會四個一循環。
作者: idontnow90    時間: 2013-6-3 22:29

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

發現有兩數字 \(0,8\) 開始重複了，

就可以確定餘數是以 \(0,8,0,2\) 的方式循環。

.
那這樣我有點搞混了ㄟ..
如果說剛剛那題目(我們先撇開那個2倍的錯誤不看..)
是\(S_n=(a^3)^n+(b^3)^n, S_1=8, S_2=2,  S_3=8, S_4=2,\)他也是連續兩數字 \(8,2\) 重複

但是現在這題\(a_n=(p^2)^n+(q^2)^n, a_1=0,a_2=8,a_3=0,a_4=2\)他也是連續兩數字 \(0,8\) 重複

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

抱歉..搞不太清楚.還請賜教.感謝~
作者: weiye    時間: 2013-6-3 23:11     標題: 回復 9# idontnow90 的帖子

你後來手寫回覆的這一題不是連續兩個數字 \(0,8\) 重複呀，

你看看你手寫的內容，明明就是 \(0,8,0,2\) 連續四個數字的重複呀。

還有你第一次回文的 \(2R_n\pmod{10}\) 是兩個數字重複沒錯，但是 \(R_n\pmod{10}\) 並不見得就會是兩個數字重複呀！

（\(2R_n\pmod{10}\) 我只是點出你並沒有充分的檢查～並不是說循環長度有誤！）
作者: idontnow90    時間: 2013-6-3 23:57

喔喔..這樣我懂了...感謝你超有耐心的說明^_^



歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0