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.

Note that while there are many pairs of integers and that satisfy this equation, there is only one pair that comes from using the Euclidean algorithm.

iamdaone
Aug 12, 2018

#4**+2 **

164x+37y=1

164=4*37+16

37=2*16+5

16=3*5+1

now substituting backwards

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= 7*164-31*37

1= 164(7) + 37(-31)

**An answer is x= 7 and y= -31**

I know it is not needed but now I will find the general solution.

1= 164(7) + 37(-31)

1= 164(7-37t) + 37(-31+164t)

x=7-37t and y=164t-31 where t is an integer.

Melody
Aug 12, 2018

#3**+2 **

Using "Extended Euclidean Algorithm", you have the following:

164x+37y=1

x =7 and y= -31

Source: **https://planetcalc.com/3298/**

Guest Aug 12, 2018

#4**+2 **

Best Answer

164x+37y=1

164=4*37+16

37=2*16+5

16=3*5+1

now substituting backwards

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= 7*164-31*37

1= 164(7) + 37(-31)

**An answer is x= 7 and y= -31**

I know it is not needed but now I will find the general solution.

1= 164(7) + 37(-31)

1= 164(7-37t) + 37(-31+164t)

x=7-37t and y=164t-31 where t is an integer.

Melody
Aug 12, 2018

#7**+2 **

This is from book VII of Euclidâ€™s Elements.

CPhill, I thought you had your own personalized copy signed by Euclid himself.

GingerAle
Aug 13, 2018

#8**+1 **

Thanks Chris,

Yes it is nifty.

Sometimes is works more easily than other times. This was a nice example. Not totally trivial but not very hard either.

The fact that it equals one makes it easier.

I spent some time practicing questions like this a while back.

It is pretty cool. Euclid was a smart cookie

Melody
Aug 14, 2018