Re: [中學] 餘數

[GaussQQ (亮)]

※ 引述《yk1224 (這是我們的紀念日)》之銘言：
:      2009
: 1.求3     除以1000之餘數為

By Euler's thm

3^(400)=1 mod 1000.
Therefore 3^2009=3^9=683 mod 1000

Rmk, if you know chinese remainder thm, you also can use it to solve it.

Let

   x=3     mod 8

   x=58      mod 125

Hint: 3^5=243=(-7) mod 125. Cosider (-7)^4 then you can get this.

Therefore, by Chinese remainder thm, you also can get the same conclusion.



: ANS:683
:      2000           4   3     2                    3     2
: 2.若(x     -1)除以(x + x  + 2x  + x + 1)之餘式為 ax  + bx  + cx +d，
:   則a+b+c+d之值?
: ANS: -6
: 第一題覺得應該是要從找規律下手
: 可是卻找不出來 囧  麻煩高手提點一下要怎麼處理
: 第二題則看到就卡了 哭哭
: 先感謝各位解惑囉!
Recall x^2+1 |x^12-1 and x^2+x+1|x^12-1 =>x^4+x^3+2x^2+x+1|x^12-1

It implies that x^2000-1=x^8-1 mod x^12-1

Therefore, x^8-1=(x^4+x^3+2x^2+x+1)(x^3-x-x+2)+-2x^3-x^2-2x-1.

So a+b+c+d=-6






--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.114.34.198
推 superlori   :真是漂亮的解法~~~大推!!!!
→ liengpi     :補個出處 99中興高中教甄 第三題 第五題
推 eqcolouring :請問為何x^2000-1=x^8-1 mod x^12-1?
→ GaussQQ     :因為x^12=1
推 yk1224      :想請問x^12 是怎麼想到的? 感恩!
→ GaussQQ     :x^2+1|x^6+1 and x^2+x+1|x^6-1