※ 引述《ad0960 (停留)》之銘言：
: 各位版友好。
: 這題我知道有兩個算法。
: 第一個是：
: 3^2+3+1=13
: 3^n（n從1到11）除13的餘數會有循環。
: 第二的算法是我有問題的：
: 定義2多項式：x^11和x^2+x+1
: 然後令x^2+x+1=0, and then (x+1)(x^2+x+1)=x^3-1=0, -> x^3=1
: -> x^11=x^2, ->將3帶到x^2裡，得3^2=9。
: 答案是9。
x^11 = (x^3 -1)*q(x) + r(x), deg(r) <= 2
Key point : 因為 x^3 - 1 是首一多項式
故 q(x), r(x) 都是整係數多項式
1 = r(1)
ω^11 = ω^2 = r(ω)
(ω^2)^11 = ω = r(ω^2)
It is obvious to see that r(x) = x^2
then
x^11 = (x^3-1)*q(x) + x^2 for all x
3^11 = (3-1)(3^2+3+1)*q(3) + 9
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.96.239
※ 編輯: JohnMash 來自: 123.194.96.239 (04/08 12:27)