# Diophantine equation

## 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 dont know how to find the linear combination of these...to obtain the particular solution. Please help

Related Calculus and Beyond Homework Help News on Phys.org
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,
Code:
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,
Code:
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,
Code:
 0    1     32
1   -1     5
-6    7     2
Again calculate the modulo part as a row operation, row1 - 2*row2, which gives,
Code:
 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$

Last edited:
chwala