Solving Diophantine equation stuck, what do I do next?

[jdnhldn]

Homework Statement

I am trying to determine if an diophantine equation is solveable or not. And got stuck at one point.

Homework Equations

61x+37y=2

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?

 

[annoymage]

Homework Statement

I am trying to determine if an diophantine equation is solveable or not. And got stuck at one point.

Homework Equations

61x+37y=2

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?

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

 

[jdnhldn]

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

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?

 

[least_action]

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?

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).

 

[jdnhldn]

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

 

[jdnhldn]

The "(n)" made me see it clearly. Thank you so much.