+0

# help!

0
240
4

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 $$x$$ and $$y$$ that satisfy this equation, there is only one pair that comes from using the Euclidean algorithm.

Oct 31, 2018

#1
+2

Set up a division problem where x is larger than y.
x/y = c with remainder R. Do the division. Then replace x with y, replace y with R and repeat the division. Continue the process until R = 0.

164 ÷ 37 = 4 R 16    (164 = 4 × 37 + 16)

37 ÷ 16 = 2 R 5    (37 = 2 × 16 + 5)

16 ÷ 5 = 3 R 1    (16 = 3 × 5 + 1)

5 ÷ 1 = 5 R 0    (5 = 5 × 1 + 0)

When remainder R = 0, the GCF is the divisor, y, in the last equation. GCF = 1

Using this online calculator: https://planetcalc.com/3298/

Gives the coefficients of  x =7    and      y = -31

(164*7) + (-31*37) = 1

1,148  +  (-1,147)    = 1

Oct 31, 2018
#2
+102803
+2

Thanks guest, my method is the same as yours but i have been asked to recreate in the way i have done in the past.

$$164x+37y=1$$

The method that guest and I both use was devised by the ancient Greek mathematician Euclid.

$$\text{Euclidean algorithm}\\ 164=4*(37)+16\\ 37=2*(16)+5\\ 16=3*(5)+1\\~\\ \text{Extended Euclidean algorith}\\ 1=16-3*(5)\\ 1=16-3*(37-2*(16))\\ 1=16-3*37+6*(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)\\$$

So    x=7  and  y=-31 is one integer solution.

The question is now answered but I will continue in order to find all the possible solutions

$$1=164(7)+37(-31)\\ 1=164(7+37n)+37(-31-164n)\\ \text{I have added and then subtracted 164*37n}\\~\\ x=7+37n\qquad and \qquad y=-31-164n \qquad For\;\; all \;\;n\in Z$$

.
Oct 31, 2018
edited by Melody  Oct 31, 2018
#3
+102422
+1

Thanks, Melody!!!

I'm adding this one to my Watchlist  for more review.....i'll try to "hardwire" this proceedure to my tiny brain.....LOL!!!

CPhill  Nov 1, 2018
edited by CPhill  Nov 1, 2018
#4
+102803
+2

Thanks Chris, it IS a pretty neat way to play with numbers.

Diophantine equations (equations with only integer solutions) are fun :)

This one is a little easier than most but they are all similar.

If you have Ax+By=C

where A, B and C are constants

I think there is only an answer if the GCD of (A,B) is also a factor of C

Melody  Nov 2, 2018
edited by Melody  Nov 2, 2018