設f(x)=x^1234+1,求2^1234除以3的餘數

f ( x ) = x^1234 + 1
f ( - 1 ) = ( - 1 )^1234 + 1
= 1 + 1
= 2
於是, ( x + 1 ) Q ( x ) + 2 = x^1234 + 1
( 2 + 1 ) Q ( 2 ) + 2 = 2^1234 + 1
2^1234 = 3 Q ( 2 ) + 1
所以2^1234除以3的餘數為1。


2008-02-02 23:24:57 補充：
下面的方法是太複雜了, 以上的方法會較為簡單: 首先證明x+1是f(x)的factor, 於是便得出(x+1)Q(x)+2=x^1234+1接著代x=2, 移項後便得出餘數為1。

2008-02-02 23:25:50 補充：
我之前也曾答過類似的問題, 有興趣可參考:http://hk.knowledge.yahoo.com/question/?qid=7007122702345

2008-02-02 23:56:38 補充：
sor, 打錯了一些句子: 首先找出f(x)除x+1的餘數, 於是便得出(x+1)Q(x)+2=x^1234+1接著代x=2, 移項後便得出餘數為1。

By Fermat's little theorem,
ap mod p = a
using a=2,p=1233 (where 1233 mod 3 = 0)
we get 21233 mod 1233=2
therefore
21234 mod 1233=2*2=4
and
21234 mod 3
=4 mod 3
=1