Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I needed (for my research) to solve a Diophantine equation, in particular, $$ 2 a + 3 b + 4 c + 5 d = 12 .$$ And I could easily solve it (for example, on solution is $a=2, b=1, c=0, d=1$). But this made me wonder if such equations, with their coefficients increasing sequences of natural numbers, are a special case of Diophantine equations that are always explicitly solvable, despite the negative solution to Hilbert's 10th problem.

share|improve this question
    
as long as some of the coefficents are relatively prime, we can use bezouts identity. –  anon Aug 6 '10 at 19:07
    
@maud: Thanks, I was ignorant of Bézout's identity, so I am glad to learn. Does the identity apply when the right-hand-side number is arbitrary? –  Joseph O'Rourke Aug 6 '10 at 19:22
    
If they are relatively prime you can solve for any number, but if they are not you can only hit multiples of the GCD. –  anon Aug 6 '10 at 20:04
2  
BTW, all multiples of the gcd can be achieved only if you allow negative values (which you probably do). If you allow only nonnegative values, only all sufficiently large multiples of the gcd can be so expressed; this is the Frobenius number or coin problem. –  ShreevatsaR Aug 6 '10 at 20:49
    
dividing through by the gcd of the coefs reduces to the case where they have gcd = 1, where you can apply Bezout. –  Bill Dubuque Aug 6 '10 at 20:52
add comment

1 Answer

up vote 8 down vote accepted

Linear Diophantine equations are always solvable decidable (in linear time). If the coefficients are $a_1, a_2, ... a_n$ then the numbers that can appear on the RHS are precisely the multiples of $\text{gcd}(a_1, ... a_n)$, and one can find solutions using the extended Euclidean algorithm.

share|improve this answer
2  
+1. Perhaps it would be better to say that linear Diophantine Equations are always "decidable", or clarify that to "solve" a Diophantine equation means to determine whether or not it has a solution. Some might think (even me, perhaps) that an equation is "solvable" if it has a solution. –  Pete L. Clark Aug 6 '10 at 21:00
    
    
Thanks, Qiaochu (& Pete & Bill & Danny et al.). I did not understand this before, but now I do! –  Joseph O'Rourke Aug 7 '10 at 0:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.