11 12
發新話題
打印

整數論的題目,同餘的題目.

推到噗浪
推到臉書

整數論的題目,同餘的題目.

題目:
若 \(\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.\)

TOP

補上出處,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 編輯 ]

TOP

想請教我的做法哪裡錯了?感謝~
\( 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 編輯 ]

TOP

回復 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}\)。

TOP

回復 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}\)

TOP

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

附件

IMG_7614.jpg (251.98 KB)

2013-6-3 21:47

IMG_7614.jpg

TOP

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

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

TOP

回復 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}\) 會四個一循環。

TOP

引用:
原帖由 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\) 重複

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

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

TOP

回復 9# idontnow90 的帖子

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

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

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

(\(2R_n\pmod{10}\) 我只是點出你並沒有充分的檢查~並不是說循環長度有誤!)

TOP

 11 12
發新話題