In addition to easily finding the gcd the Euclidean algorithm does something else.Let'ssee how this works for our example.We now know that (3589,2522) = 97 which meansthat we know that there must be integers m and n such that 3589m+ 2522n = 97 .Theproof of this is a purely theoretical result that gives no hint as to how to find theseintegers.But the Euclidean algorithm finds them for us!Let's see how this works.We will start with the last equation 388

In addition to easily finding the gcd the Euclidean algorithm does something else.Let's
see how this works for our example.We now know that (3589,2522) = 97 which means
that we know that there must be integers m and n such that 3589m+ 2522n = 97 .The
proof of this is a purely theoretical result that gives no hint as to how to find these
integers.But the Euclidean algorithm finds them for us!Let's see how this works.
We will start with the last equation 388 = 291×1+ 97 .From this equation we were able to
conclude that (388,291) = 97 but it is also easy to see that we can use the equation to
write 97 as a linear combination of 388 and 291.We just solve for 97 to get:
(*) 97 = 388×(1) + 291×(-1)
We can now use the previous equation 1067 = 388× 2 + 291 to express 291 as a linear
combination of 1067 and 388.
(**) 291 =1067×(1) + 388×(-2)
We now use (**) to substitute into (*) to express 97 as a linear combination of 388 and
1067.
(***) 97 = 388×(1) + [1067×(1) + 388×(-2)] ×(-1) = 388(3) +1067 ×(-1)
We can now use the equation 2522 =1067 ×2 + 388 to express 388 as a linear
combination of 2522 and 1067 and then substitute that into (***) to express 97 as a linear
combination of 2522 and 1067.
最后问题是：
Exercise 9:Continue this process until you have found the integers m and n so that
3589m+ 2522n = 97