+94 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.
+118609 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.
Using "Extended Euclidean Algorithm", you have the following:
164x+37y=1
x =7 and y= -31
Source: https://planetcalc.com/3298/
+118609 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.
+128475 That's pretty nifty, Melody... I don't think I am familiar with this !!!
+2440 This is from book VII of Euclid’s Elements.
CPhill, I thought you had your own personalized copy signed by Euclid himself.
+118609 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
