Use the Euclidean algorithm to find integers $x$ and $y$ such that $164x + 37y = 1.$ State your answer as a list with $x$ first and $y$ seco

Im going to try to solve this using a new technique I'm practicing ......Diophantine Equations...

First....use the Euclidian Algorithm to generate a sequence of quotients starting with the coefficients of the given equation......so we have

164 = 4(37) + 16

37 = 2(16) + 5

16 = 3(5) + 1

5 = 4(1) + 1

1 = 1(1) + 0

Write a three row table, thusly......

          4     2     3     4     1

1 0     1     2     7    30    37

0 1     4     9    31  133  164

The top line is just the quotients (in bold) that we found in the Euclidian Algorithm

The        1 0

              0 1     

matrix is a starting point for generating the rest of the table......each entry in the the table is found - working left to right - by multiiplying the number at the top of the columm by the entry to the immediate left of where our entry is to be placed, and then adding the number found two cells to the left of where our entry is to be placed... .......for instance......the "9"  entry in the table is generated by multiplying the number at the top of the column (2) times the number immediately to the left of the cell where the "9" will go....in this case, that number is 4....to this product we add the number two cells to the left of where the "9" will go....in this case that number is "1"......so we have 2(4) + 1 = 9  

The entries in the last column should be the coefficients in our equation...if not....we've made a mistake  !!!

The general solution comes from the determnant of the 2 x 2 matrix in the last two columns, i. e.,  the matrix....

30        37

133    164

Taking the determinant, we have   164*30  - 37*133  = -1

However, we  need a "1".....so multiplying by -1 all the way through, we have 

164(-30) + 37(133) = 1    (It should be noted that this determinant will always be either a "1" or a "-1" )

So.....we have one solution  x = -30  and y = 133

However......because this is linear....it will have infinite solutions....and all of them can be described by the general form ....[(x + bk), (y - ak) ]  =   [ (-30 + 37k ), (133 - 164k) ]  where k is any integer.......

[This form is generated by the fact that ..... ax + by = a(x+bk) + b(y-ak) ]

Note one other fact about this type of equation..... ax + by = c  ......if a, b have a common factor not shared by c, there are no integer solutions  !!!!!   In our case....164 and 37 are co-prime......

I need to practice diophantine equations too.  

Thanks for providing us with one Mellie.

You always provide us with great questions. :)

Although of course we are asked to use the Euclidian algorithm (whatever that may be)

If I get around to it I will look it up later :)