I am reading that Euclid's algorithm can give you two integers, S and T such that the greatest common factor for two integers N and M gcf(M,N) = SM + TN ... but this seems mathematically impossible. Is this a typo in the book? How does this work? Example, gcf(12,16) is 4. Simple. But there are no positive integers S and T such that 12S + 16T = 4. What am I missing?

Question

I am reading that Euclid's algorithm can give you two integers, S and T such that the greatest common factor for two integers N and M gcf(M,N) = SM + TN ... but this seems mathematically impossible.  Is this a typo in the book?  How does this work?  Example, gcf(12,16) is 4.  Simple.  But there are no positive integers S and T such that 12S + 16T = 4.  What am I missing?

loser66 · Answer

You can apply matrix method to find it out 
|1  0  16|                       | 1  -1  4|                           | 1 -1  4|
| 0  1  12| -R2 +R1 --> | 0  1  12| and -3*R1 +R2  | -3  4  0|
which gives us 4 = 1(12) + (-1) 16 
therefore, S =1 and T =-1 
We can't have both them are positive.

loser66 · Answer

Other way is algebraic way
gcd( 12, 16)
16 = 1(12) +4
 12 = 3(4) +0
so gcd (12,16) =4