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$ second, separated by a comma. $$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$ second, separated by a comma.$$

Mellie
Jun 28, 2015

#1**+10 **

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 ..... a*x* + b*y* = 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......

CPhill
Jun 29, 2015

#1**+10 **

Best Answer

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 ..... a*x* + b*y* = 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......

CPhill
Jun 29, 2015