+1836 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. UsetheEuclideanalgorithmtofindintegers$x$and$y$suchthat$164x+37y=1.$Stateyouranswerasalistwith$x$firstand$y$second,separatedbyacomma.
+130458 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......
+130458 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......
