+0  
 
0
133
2
avatar+53 

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.

 Mar 17, 2021
 #1
avatar+121004 
+3

Here's what I came up with a while  back :

 

 

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

 Mar 17, 2021
 #2
avatar
0

Thank you very much! This one stumped me for a long time :)

Guest Mar 17, 2021

12 Online Users