Answer:
52
Explanation:
Let a = 19 and m = 141
Step 1: Find the gcd(141, 19).
We do this using the Euclidean Algorithm
This takes advantage of the fact that if
a = bq + r for a, b, q, r ∈ Z, then gcd(a, b) = gcd(b, r).
Using this algorithm we get:
141 = 7 · 19 + 8 gcd(141, 19) = gcd(19, 8)
19 = 2 · 8 + 3 = gcd(8, 3)
8 = 2 · 3 + 2 = gcd(3, 2)
3 = 1 · 2 + 1 = gcd(2, 1)
2 = 2 · 1 + 0 = 1
Therefore, 141 and 19 are relatively prime and 19 mod 141 has an inverse.
The modular inverse of 19 mod 141 is 52.