[Math] Does someone see the mistake when calculating inverse of 34 mod 89

Question

This is from Discrete Mathematics and its Applications

I am doing 6b. The method in example 2 is basically using Euclid's Algorithm to make sure that the greatest common divisor is 1 and then back substituting to find Bezout coefficients. Here's my work so far

First Euclid's Algorithm
89 = 34(2) + 21
34 = 21(1) + 13
21 = 13(1) + 8
13 = 8(1) + 5
8 = 5(1) + 3
5 = 3(1) + 2
3 = 2(1) + 1
2 = 1(2) + 0

Because 1 is the last remainder before it hits 0, it is the gcd, meaning the inverse of 34 modulo 89 exists.

And then back substituting

1 = 3 – 1(2)
1 = 3 – 1 (5 – 3(1))
1 = -5 + 2(3)
1 = -5 + 2(8 – 5(1))
1 = 2(8) + (-3)(5)
1 = 2(8) + (-3)(13 – 8(1))
1 = (-3)(13) + (-1)(8)
1 = (-3)(13) + (-1)(21 – 13(1))
1 = (-1)(21) + (-2)(13)
1 = (-1)(21) + (-2)(34 – 21(1))
1 = (-2)(34) + (1)(21)
1 = (-2)(34) + (1)(89 – 34(2))
1 = (-4)(34) + (1)(89)
From here I can see that -4 is the inverse because it is the coefficient of a.
So I represented the inverse in this notation
(-4)(34) $\equiv$ 1 mod(89)
but -4 * 34 = -136 – 1 = -137 which isn't a multiple of 89…. Does anyone see the issue? Even when I typed this, I didn't see any arithmetic issue.

Answer 1

Your mistake is at this position:

1 = 2(8) + (-3)(13 - 8(1))
1 = (-3)(13) + (-1)(8)