+0  
 
+5
109
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.

iamdaone  Aug 12, 2018

Best Answer 

 #4
avatar+93866 
+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
 #1
avatar+144 
+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!

azsun  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/

Guest Aug 12, 2018
 #4
avatar+93866 
+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+91027 
+1

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

 

 

cool cool cool

CPhill  Aug 13, 2018
 #7
avatar+1198 
+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+93866 
+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+91027 
+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+1198 
+2

Sisyphus is one smart cookie too.smiley

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

thanks!!

iamdaone  Aug 12, 2018

11 Online Users

avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.