2012-09-05

〔離散〕數論p1-78 ex12


請教諸位高手,紅字問號地方為什麼是3,我算的是-2,以下是我的算法
42 = 8x5+2
5 = 2x2+1
  1 = 5-2x2
    =>5-2x(42-8x5)
   =>-2x42+9x5
所以42^-1=-2(mod 5)
請問我是哪裏有錯

5 則留言:

Bruce 提到...

其實-2同餘3同餘1 mod 5,所以-2跟3都是對的(抱歉同餘符號不會打)(你代兩個答案進去驗算就知道了)。不過inerse of N課本解答比較喜歡寫最小正整數,我想是因為畢竟最後答案都要寫成最小正整數為佳。

tomato 提到...

所以M4也可寫成4 (mod 7)這樣也對嗎

tomato 提到...

我同餘3 x=173
mod 5 x同餘3 =>1 成立
但我同餘-2
x=1x1x105+3x(-2)x42+5x(-3)x30=-460
mod 5 並不等餘 1 而是 餘0
所以你確定 同餘-2 跟同餘 3是一樣的嗎

tomato 提到...

抱歉,是我算錯了
x=1x1x105+3x(-2)x42+5x(-3)x30=-443
所以同餘-2 跟同餘 3(mod 5)是一樣沒錯

tomato 提到...

再更正
x=1x1x105+2x1x70+3x(-2)x42+5x(-3)x30=>-443