1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook