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