打印

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

weiye

瑋岳

發私訊
加為好友
目前離線

1^# 大中小發表於 2009-6-24 21:41 只看該作者

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

題目：
若 Rn=21

an+bn

，其中 a=3+2

2

b=3−2

2 ，且 n=0

1

2

3

。試問 R12345 的個位數為何？

解答：

因為 a+b=6 且 ab=1，所以 a

b 為 x2−6x+1=0 的兩根，

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

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

n=0

1

2

3

an+2+bn+2

−6

an+1+bn+1

+

an+bn

=0

n=0

1

2

3

21

an+2+bn+2

−6

21

an+1+bn+1

+21

an+bn

=0

n=0

1

2

3

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

n=0

1

2

3

Rn+2=6Rn+1−Rn

n=0

1

2

3

且由 R0=1

R1=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

多喝水。

TOP

bugmens

發私訊
加為好友
目前離線

2^# 大中小發表於 2009-6-25 06:39 只看該作者

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

TOP

idontnow90

發私訊
加為好友
目前離線

3^# 大中小發表於 2013-6-2 23:59 只看該作者

想請教我的做法哪裡錯了?感謝~
a3+b3=198

a3

b3=1

2Rn=(a3)n+(b3)n
2R1=a3+b3=198
2R2=a6+b6=1982−2==

2
2R3=a9+b9==

198

2−1

198==

8
so

R為2循環:4

1

4

1

所求為n=4115時

所以答案為4

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

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

4^# 大中小發表於 2013-6-3 00:24 只看該作者

回復 3# idontnow90 的帖子

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

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

另外， 2

某數

8(mod10)，並不保證某數

4(mod10)

例如：2

9

8(mod10)，但是「9 並不同餘 4(mod10)」

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

即「不存在整數 a，使得 a

2

1(mod10)」，

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

多喝水。

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

5^# 大中小發表於 2013-6-3 08:17 只看該作者

回復 1# weiye 的帖子

另解：

因為

3

2

3=99

70

2

所以 21

3+2

2

12345+

3−2

2

12345

　　　=21

99+70

2

4115+

99−70

2

4115

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

　　　

994115(mod10)

　　　

−1

4115(mod10)

　　　

−1(mod10)

　　　

9(mod10)

多喝水。

TOP

idontnow90

發私訊
加為好友
目前離線

6^# 大中小發表於 2013-6-3 21:08 只看該作者

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

附件

IMG_7614.jpg (251.98 KB)

2013-6-3 21:47

TOP

idontnow90

發私訊
加為好友
目前離線

7^# 大中小發表於 2013-6-3 21:35 只看該作者

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

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

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

8^# 大中小發表於 2013-6-3 21:50 只看該作者

回復 7# idontnow90 的帖子

這樣寫會對沒錯呀，

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

8

0

2

0

8

發現有兩數字 0

8 開始重複了，

就可以確定餘數是以 0

8

0

2 的方式循環。

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

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

或是再加上簡單說明 an=10an−1−an−2

an

−an−2(mod10)

an

−an−2

an−4(mod10)

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

多喝水。

TOP

idontnow90

發私訊
加為好友
目前離線

9^# 大中小發表於 2013-6-3 22:29 只看該作者

引用:

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

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

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

.

那這樣我有點搞混了ㄟ..
如果說剛剛那題目(我們先撇開那個2倍的錯誤不看..)
是Sn=(a3)n+(b3)n

S1=8

S2=2

S3=8

S4=2

他也是連續兩數字 8

2 重複

但是現在這題an=(p2)n+(q2)n

a1=0

a2=8

a3=0

a4=2他也是連續兩數字 0

8 重複

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

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

TOP

weiye

瑋岳

發私訊
加為好友
目前離線

10^# 大中小發表於 2013-6-3 23:11 只看該作者

回復 9# idontnow90 的帖子

你後來手寫回覆的這一題不是連續兩個數字 0

8 重複呀，

你看看你手寫的內容，明明就是 0

8

0

2 連續四個數字的重複呀。

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

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

多喝水。

TOP