整數論的題目，同餘的題目.
題目：若 \(\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\)，就可以開始條列，如下
[table=50%][tr][td] \(n\)[/td][td] 0[/td][td]1
[/td][td]2
[/td][td]3
[/td][td]4
[/td][td]5
[/td][td]6
[/td][td]7
[/td][/tr][tr][td] \(R_n\) 除以\(10\)的餘數
[/td][td]1
[/td][td]3
[/td][td]7
[/td][td]9
[/td][td]7
[/td][td]3
[/td][td]1
[/td][td]3
[/td][/tr][/table]
列到開始有兩位數字跟前面一樣，就可以停止了（因為由遞迴關係式可知，每一項只與前兩項有關，故若前兩項相同，後面的結果亦相同）
由上表可以知道 \(R_n\) 除以 \(10\) 的餘數每六個數字一循環，而 \(12345\) 除以 \(6\) 的餘數為 \(3\)，
故，\(R_{12345}\) 除以 \(10\) 的餘數\(=R_3\) 除以 \(10\) 的餘數\(=9.\) 補上出處，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} \)
[[i] 本帖最後由 bugmens 於 2009-6-25 06:42 AM 編輯 [/i]]
頁:
[1]