# Solving Diophantine equation stuck, what do I do next?

1. Sep 9, 2010

### jdnhldn

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. Sep 9, 2010

### annoymage

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

3. Sep 10, 2010

### jdnhldn

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?

4. Sep 10, 2010

### least_action

You can always solve $$ax + by = k \text{gcd}(a,b)$$ (This is Bezout's identity and it is solved using the Euclidean algorithm).

Clearly if $$x',y'$$ solves $$ax' + by' = \text{gcd}(a,b)$$ then $$x = kx', y = ky'$$ solves $$ax + by = k \text{gcd}(a,b)$$, Thus you only have to work on $$ax' + by' = \text{gcd}(a,b)$$, you can use the hint annoymage gives to prove this once and for all (as well as calculate $$x'$$ and $$y'$$ in specific cases where the numbers are given).

5. Sep 11, 2010

### jdnhldn

Thank you, I've got it. Now I saw the lights.

6. Sep 12, 2010

### jdnhldn

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