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. cookie policy and privacy policy.
 
+0  
 
0
138
3
avatar

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

 Dec 23, 2018
 #1
avatar+100516 
+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)

 

 

cool cool cool

 Dec 23, 2018
 #3
avatar
+1

Yes, this is correct.  Thanks @CPhill

Guest Dec 23, 2018
 #2
avatar+4221 
+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)}.\)

.
 Dec 23, 2018

10 Online Users

avatar