We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website.
Please click on "Accept cookies" if you agree to the setting of cookies. Cookies that do not require consent remain unaffected by this, see
cookie policy and privacy policy.
DECLINE COOKIES

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.)

Guest Dec 23, 2018

#1**+2 **

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)

CPhill Dec 23, 2018

#2**+1 **

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)}.\)

.tertre Dec 23, 2018