Using the extended Euclidean algorithm, find the multiplicative inverse of

a. 650 mod 1869

b. 1035 mod 3321

c. 9141 mod 39902

Note: Explain the reason if the multiplicative inverse does not exist. Alternatively, provide a table similar to Table 2.4 in the textbook. Feel free to write a computer program to fill in the entries of the table and, if you do so, attach your code to your answer.

 

2.4 / PRIME NUMBERS 61 Table 2.4 Extended Euclidean Algorithm Example i ri li X; Yi -1 1759 1 550 1 1 109 1 -3 2 -5 16 3 4 21 106 -339 4 1 1 -111 355 5 0. 4 Result: d = 1; x = -111; y = 355 3.