多項式除法問題

試問3^11 除以3^2+3+1 之餘數為何？
(A) (B) 3 (C) 9 (D) 12
Sol
3^2+3+1=13
3^11
=>(3*3)^3*9
=>(27^3)*9
=>(2*13+1)^3*9
=>(1^3)*9
=>9
(C)

首先我換個題目
(1) 試問f(x) =x^11 除以p(x)=x^2+x+1 之餘式r(x)為何？
(2) x=3時, r(3)=?

這才是題目想測驗你的目的,不是要你直接除以13啊.

否則萬一題目改成
1998^11 除以1998^2+1998+1 之餘數為何？
你慢慢乘除吧.

---------------------------------------------------------------------------------------
正解 f(x) = p(x)*Q(x) + r(x)
令 x^2+x+1 = 0 => (x-1)(x^2+x+1) = 0 => x^3 -1 =0 => x^3 =1
所以 x^11 = (x^3)3* x^2 = 1*x^2 = x^2
x=3時, r(3)= 3^2 = 9 -------- (C)

只可能是你除錯了
3^11=(3^3)^3*(3^2)≡3^2≡9(mod 13)

2012-05-18 06:34:46 補充：
x^11=(x^3-1)q(x)+x^2=(x^2+x+1)[(x-1)q(x)+1]-x-1
x=3帶入，得
3^11=(3^2+3+1)[2q(3)+1]-4
餘數=-4≡9(mod 13)