1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Diophantine equation

  1. Sep 13, 2012 #1
    1. The problem statement, all variables and given/known data
    Solve [tex]57x+4y=2[/tex]
    2. Relevant 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
    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 dont know how to find the linear combination of these...to obtain the particular solution. Please help
  2. jcsd
  3. Sep 13, 2012 #2


    User Avatar
    Science Advisor

    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,
    Code (Text):

    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 (Text):

    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 (Text):

     0    1     32
     1   -1     5
    -6    7     2
    Again calculate the modulo part as a row operation, row1 - 2*row2, which gives,
    Code (Text):

     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]
    Last edited: Sep 13, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook