Euclid's Algorithm Question

[PeterRobinson44]

Euclid's algorithm returns
gcd(14, 33) = 1 = 3 · 33 - 7 · 14.

What is the multiplicative inverse of 14 in Z33?

I know the answer is 26. Because -7 is the coefficient of 14. -7 mod 33 = 26.

However, can we run through where the 3 · 33 - 7 · 14 comes from. I know GCD(14,33) is equal to 1. But finding how they got 3 · 33 - 7 · 14 is what I am having a difficult time with. Thank you very much in advance.

 

[HallsofIvy]

The "multiplicative inverse of 14 in Z33" is the number x such that 14x= 1 (mod 33) which is the same as saying that 14x is 1 more than some multiple of 33. That is, 14x= 1+ 33y for some integers x and y. That is the same as the "Diophantine equation" 14x- 33y= 1.

To solve that, note that 14 divides into 33 twice with remainder 5: 33- (2)14 = 5. And 5 divides into 14 twice with remainder 4: 14- 2(5)= 4. And, finally, 4 divides into 5 once with remainder 1: 5- 4= 1.
So, 5- (14- 2(5))= 3(5)- 14= 1, 3(33- 2(14))- 14= 3(33)- 7(14)= 1. You can check that: 3(33)- 7(14)= 99- 98= 1.

Compare "3(33)- 7(14)= 1" with "14x- 33y= 1". Do you see that x= -7, y= -3 is a solution? Of course, here we want x to be between 0 and 33. It is easy to see that 14(x+ 33k)- 33(y+ 14k)= 14x+ (14)(33k)- 33y- (33)(14k)= 14x- 33y= 1 for all k. What value of k makes -7+ 33k between 0 and 33? Obviously k= 1 gives x= -7+ 33= 26.

Check: 14*26= 364= 11*33+ 1. Yes, the multiplicative inverse of 14 (mod 33) is 26.