+0

# Help ASAP!

+5
240
10
+95

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.

Aug 12, 2018

#4
+100800
+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.

Aug 12, 2018

#1
+183
+1

Yes, the Euclidean Algorithm!

164x+37y=1

So, x/y=164/37= 4 R 16, so 164=37*4+16.

Now, we have x/y=37/16= 2 R 5, so 37=16*2+5.

Next, x/y=16/5=3 R 1, so 16=5*3+1.

After that, x/y=5/1= 5 R 0, so 5=1*5+0.

Try to finish it!

Aug 12, 2018
edited by azsun  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/

Aug 12, 2018
#4
+100800
+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
#6
+100483
+1

That's pretty nifty, Melody... I don't think I am  familiar with this  !!!

CPhill  Aug 13, 2018
#7
+1414
+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
+100800
+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
#9
+100483
+1

LOL!!!.....I did have a "personalized" copy, once....but I think Sisyphus absconded with it in his search for the Roman "zero"

CPhill  Aug 14, 2018
#10
+1414
+2

Sisyphus is one smart cookie too.

GingerAle  Aug 14, 2018
#5
+95
+6

thanks!!

Aug 12, 2018