大學離散數學~求解

2014-07-15 11:08 pm

1.Find an inverse of a modulo m for each of these pairs of relatively prime integers.
(a) a = 4, m = 9
(b) a = 19, m = 141
(c) a = 55, m = 89
(d) a = 89, m = 232

2.Solve each of these congruences using the modular inverses found in part (b), (c), (d) of
last question.
(a) 19x ≡ 4(mod141)
(b) 55x ≡ 34(mod89)
(c) 89x ≡ 2(mod 232)

3.(a) Using Fermat’s little theorem to compute 52003 mod 7, 52003 mod 11, 52003 mod 13.
(b) Use your results from part (a) and the Chinese remainder theorem to find 52003 mod
1001. (Note that 1001=7‧11‧13)

更新1:

自由自在: 感謝您的解答，第三小題答案似乎跟正解不太一樣。

回答 (3)

用戶9112

2014-07-16 6:48 am

✔ 最佳答案

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

圖片參考：https://s.yimg.com/rk/HA05107138/o/1523997141.png

圖片參考：https://s.yimg.com/rk/HA05107138/o/1633336982.png

圖片參考：https://s.yimg.com/rk/HA05107138/o/475221897.png

2014-07-17 15:51:44 補充：
你的正解怎麼說???

👍 0 👎 0

[匿名]

2014-07-17 8:16 pm

感謝您的熱心解答。3q

👍 0 👎 0

Sam

2014-07-16 10:03 pm

(b) a = 19, m = 141 求1/a=1/19=?
[sol]
由 19 和 141 互質知道存在x 和 y
使得
19x+141y=1 ….(1)
成立。
式(1) Mod 141 得
19x=1 (mod141)
x=1/a=1/19 (mod141)

2014-07-16 14:04:20 補充：
x 和 y 有一定的程序可以求得，程序如下:
對141和 19利用輾轉相除法可以得到:
8=141-19*7 …(2)
3=19-8*2 …(3)
2=8-3*2 …(4)
1=3-2*1 …(5)
由最後一式(5)反代回去可以得到:
1=3-2*1 {2用(4) 代入}
=3-(8-3*2)*1 {整理}
=3*3-8 {3用(3) 代入}
=(19-8*2)*3-8 {整理}
=19*3-8*7 {8用(2) 代入}
=19*3-(141-19*7)*7{整理}
=19*52-141*7

2014-07-16 14:04:42 補充：
重寫:
1=19*52-141*7
=19*52 (mod 141)
所以
x=1/a=1/19=52 (mod 141)

2014-07-16 14:06:54 補充：
(c) a = 55, m = 89
(d) a = 89, m = 232
可以如法炮製，請自己練習。

👍 0 👎 0

收錄日期: 2021-04-27 21:15:11
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20140715000010KK07188

檢視 Wayback Machine 備份