+0  
 
0
47
4
avatar

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.

Guest Oct 31, 2018
 #1
avatar
+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

Guest Oct 31, 2018
 #2
avatar+93866 
+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\)

Melody  Oct 31, 2018
edited by Melody  Oct 31, 2018
 #3
avatar+91027 
+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!!!

 

 

 

cool cool cool

CPhill  Nov 1, 2018
edited by CPhill  Nov 1, 2018
 #4
avatar+93866 
+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

31 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.