Solving 57x+4y=2: Diophantine Equation Homework

[rayman123]

Homework Statement

Solve $$57x+4y=2$$

Homework Equations

I use the equation $$57x+4y=1$$ find
$$gcd(57,4)$$ as follows
$$57=14\cdot 4+1$$ then $$gcd(57,4)=1$$ and
$$1=57-4\cdot 14$$ so the particular solution to my first equation is
$$x_{0}=2$$*and $$y_{0}=-28$$
Wolfram says it is correct but I am not sure if the Euclidean algorithm is computed correctly

If for example I have now
$$37x+32y=3$$
is the computation of gcd(37,32) correct?
$$37=32\cdot 1+5$$
$$32=5\cdot 6+2$$
$$5=2\cdot 2+1$$
but now I don't know how to find the linear combination of these...to obtain the particular solution. Please help

 

[uart]

Hi Rayman. The Euclidean algorithm is essentially just the iterative application of $\gcd(a,b) = \gcd(b,a \mod b)$ (for $a \geq b$), but with the modulo operation tracked as a series of row operations. It's easiest to explain by way of your example.

Say we want to solve $37x + 32y = 1$.

Write it like a matrix as in,

1   0     37
0   1     32

where this represents 1x + 0y = 37, and 0x + 1y = 32.

Now we calculate the modulo part as a row operation, row1 - 1*row2, which gives,

1   0     37
0   1     32
1  -1     5

BTW. I'm going to be lazy here and just keep referring to row1 and row2 as the most recent two rows ok.

Again calculate the modulo part as a row operation, row1 - 6*row2, which gives,

 0    1     32
 1   -1     5
-6    7     2

Again calculate the modulo part as a row operation, row1 - 2*row2, which gives,

 1    -1      5
-6     7      2
13   -15      1

So finally, just using a series of row operations we have deduced that $13 \times 37 - 15 \times 32 = 1$