Question

Transcribed image text: (a) Compute the multiplicative inverse of 16 (mod 173). Use the Extended Euclidean algorithm, showing the tableau and the sequence of substitutions. Express your final answer as an integer between 0 and 172 inclusive. [6 points] (b) Find all integer solutions to 16x = 12 (mod 173) You may use part (a) without repeating explanations from there. Your final answer must be in set-builder notation (for example {z: = k. 121 + 13 for some k € Z}), and you must show work for how you find the expression in your set-builder notation. [8 points]

Answer 1

To compute the multiplicative inverse of 16 (mod 173) using the Extended Euclidean algorithm , we first write out the table for the algorithm as follows:

r r' q s s' t t'

0 173 1 0

1 16

2 13

3 3 1 1

4 1 3 4

5 0 1 101

We start by initializing the first row with r = 173, r' = empty, q = empty, s = 1, s' = empty, t = 0, and t' = empty. Then we set r = 16, and fill in the second row with r = 16, r' = empty, q = empty, s = empty, s' = empty, t = empty, and t' = empty. Next, we divide 173 by 16 to get a quotient of 10 with a remainder of 13. We fill in the third row with r = 13, r' = 173, q = 10, s = empty, s' = 1, t = empty, and t' = 0. We continue this process until we get a remainder of 0. The final row will have r = 0, r' = 1, q = 101, s = empty, s' = 85, t = empty, and t' = -1. The multiplicative inverse of 16 (mod 173) is therefore 85, since 16 * 85 (mod 173) = 1.

To find all integer solutions to 16x = 12 (mod 173), we first use the result from part (a) to find the multiplicative inverse of 16 (mod 173), which we know is 85. Then we

Step-by-step explanation: