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.
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
+118609 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\)
+118609 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
