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

[rayman123]

Homework Statement

Solve [tex]57x+4y=2[/tex]

Homework Equations

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

If for example I have now
[tex]37x+32y=3[/tex]
is the computation of gcd(37,32) correct?
[tex]37=32\cdot 1+5[/tex]
[tex]32=5\cdot 6+2[/tex]
[tex]5=2\cdot 2+1[/tex]
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 [itex]\gcd(a,b) = \gcd(b,a \mod b)[/itex] (for [itex]a \geq b[/itex]), 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 [itex]37x + 32y = 1[/itex].

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 [itex]13 \times 37 - 15 \times 32 = 1[/itex]