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**+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**+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

#4**+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