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.
(I know it is a repost of https://web2.0calc.com/questions/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, but the answer was incorrect.)
+128475 164x + 37y = 1
164 = 4*37 + 16
37 = 2*16 + 5
16 = 3*5 + 1
Working backwards, we have
1 = 16 - 3(5)
1 = 16 - 3[ 37 - 2(16) ]
1 = -3(37) + 7(16)
1 = -3(37) + 7 [ 164 - 4*37 ]
1 = -3(37) + 7(164) - 28 (37)
1 = 164(7) + 37(-31)
(x, y) = (7, -31)
+4609 This sounds kind of hard, CPhill's answer seems perfectly fine to me.
Right off the bat, we see that 164 and 37 are relatively prime, We also see that 164 is 21 less than a multiple of 37. So, we can switch, 37y+164x=1, and 164 is 15 less than a multiple of 37, so 37y+185x-21x=1, 37y+185x=1+21x. Now, we can factor out 37, yielding us with 37(5x+y)=1+21x. So, 1+21x has to be a multiple of 37. So, x can be 21x+1=148, 21x=147 and x=7. Substituting it back, we see that \(y=\frac{-1147}{37}=-31.\) Thus, the answer is \(\boxed{(7,-31)}.\)
