+0  
 
+5
194
10
avatar+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

Best Answer 

 #4
avatar+99333 
+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
avatar+175 
+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
avatar
+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
avatar+99333 
+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
 #6
avatar+98173 
+1

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

 

 

cool cool cool

CPhill  Aug 13, 2018
 #7
avatar+1367 
+2

This is from book VII of Euclid’s Elements.

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

GingerAle  Aug 13, 2018
 #8
avatar+99333 
+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   laugh

Melody  Aug 14, 2018
 #9
avatar+98173 
+1

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

 

 

cool cool cool

CPhill  Aug 14, 2018
 #10
avatar+1367 
+2

Sisyphus is one smart cookie too.smiley

GingerAle  Aug 14, 2018
 #5
avatar+95 
+6

thanks!!

 Aug 12, 2018

3 Online Users

avatar