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!

Solving Diophantine equation stuck, what do I do next?

  1. Sep 9, 2010 #1
    1. The problem statement, all variables and given/known data
    I am trying to determine if an diophantine equation is solveable or not. And got stuck at one point.

    2. Relevant equations
    61x+37y=2

    3. The attempt at a solution
    I've found the gcd(61,37)=1 by:

    61/37=1 %24
    37/24=1 %13
    24/13=1 %11
    13/11=1 %2
    11/2=5 %1
    2/1=2 %0

    So gcd(61,37)=1

    I know that I now should go backwards and express gcd(61,37) as a linear combination of61 and 37. But I don't understand it?
     
  2. jcsd
  3. Sep 9, 2010 #2
    you should do like this, it maybe help to see

    61 = (1)37 + 24
    37 = (1)24 + 13
    24 = (1)13 + 11
    13 = (1)11 + 2
    11 =(5)2 +1

    so 1 = 11 - (5)2

    you know 2 = 13 - (1)11 and 11 = 24 - (1)13 and similar to 13 and 24

    just play with the numbers until you get the form 1 = (...)61 + (...)37
     
  4. Sep 10, 2010 #3
    Thank you, but is there a quick way to see if the equation is solvable or not? Or do I need to go all the way to find out?
     
  5. Sep 10, 2010 #4
    You can always solve [tex]ax + by = k \text{gcd}(a,b)[/tex] (This is Bezout's identity and it is solved using the Euclidean algorithm).

    Clearly if [tex]x',y'[/tex] solves [tex]ax' + by' = \text{gcd}(a,b)[/tex] then [tex]x = kx', y = ky'[/tex] solves [tex]ax + by = k \text{gcd}(a,b)[/tex], Thus you only have to work on [tex]ax' + by' = \text{gcd}(a,b)[/tex], you can use the hint annoymage gives to prove this once and for all (as well as calculate [tex]x'[/tex] and [tex]y'[/tex] in specific cases where the numbers are given).
     
  6. Sep 11, 2010 #5
    Thank you, I've got it. Now I saw the lights.
     
  7. Sep 12, 2010 #6
    The "(n)" made me see it clearly. Thank you so much.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving Diophantine equation stuck, what do I do next?
Loading...