a. We have GCD(34, 89) = 1; using the Euclidean algorithm,
89 = 2•34 + 21
34 = 1•21 + 13
21 = 1•13 + 8
13 = 1•8 + 5
8 = 1•5 + 3
5 = 1•3 + 2
3 = 1•2 + 1
b. Working backwards,
1 = 3 - 2
1 = 3 - (5 - 3) = 2•3 - 5
1 = 2•(8 - 5) - 5 = 2•8 - 3•5
1 = 2•8 - 3•(13 - 8) = 5•8 - 3•13
1 = 5•(21 - 13) - 3•13 = 5•21 - 8•13
1 = 5•21 - 8•(34 - 21) = 13•21 - 8•34
1 = 13•(89 - 2•34) - 8•34 = 13•89 - 34•34
c. Using the linear combination find in part b,
1 ≡ 13•89 - 34•34 (mod 89)
1 ≡ (-34)•34 (mod 89)
and
-34 ≡ -34 + 89 ≡ 55 (mod 89)
So, the inverse of 34 modulo 89 is 55.
d. Multiply both sides of the congruence by the inverse of 34:
55•34x ≡ 55•53 (mod 89)
x ≡ 2915 ≡ 32•89 + 67 ≡ 67 (mod 89)
