大學離散數學~求解

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)