Matrix method to solve linear Diophantine equations?

Question

I see in this document the following method to solve the Diophantine equation $1234x+2341y=1$:

It looks pretty useful and interesting, but I don't know what the cited work MNZ p.218 is. Can anyone tell me how this method works?

Answer 1

MNZ refers to Montgomery, Niven, Zuckerman. Your method is presented in Chapter 5, Section 1, pages 212-218 in the Fifth Edition. Your example begins with two coprime numbers, so the final diagram finishes the problem. The problem shown at the top of page 218 deals with a gcd of 3, a little extra work needed.

Instead of row operations, they are using column operations, building one step at a time. Begin with row vector $r = (1234, 2341)$ and construct square matrix $M$ such that $rM = (0,1).$ Here we have constructed $\det M = \pm 1.$ It follows that the dot product of $r$ with the right hand column of $M$ is $1.$ Furthermore, the dot product of $r$ with the left column of $M$ is zero, so we may freely add any multiple (they use $t$) of the left column of $M$ and still have a solution.