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.

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