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.

  • $\begingroup$ as long as some of the coefficents are relatively prime, we can use bezouts identity. $\endgroup$ – anon Aug 6 '10 at 19:07
  • $\begingroup$ @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? $\endgroup$ – Joseph O'Rourke Aug 6 '10 at 19:22
  • $\begingroup$ If they are relatively prime you can solve for any number, but if they are not you can only hit multiples of the GCD. $\endgroup$ – anon Aug 6 '10 at 20:04
  • 3
    $\begingroup$ 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. $\endgroup$ – ShreevatsaR Aug 6 '10 at 20:49
  • 1
    $\begingroup$ dividing through by the gcd of the coefs reduces to the case where they have gcd = 1, where you can apply Bezout. $\endgroup$ – Bill Dubuque Aug 6 '10 at 20:52

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.

  • 3
    $\begingroup$ +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. $\endgroup$ – Pete L. Clark Aug 6 '10 at 21:00
  • $\begingroup$ See also: en.wikipedia.org/wiki/B%C3%A9zout%27s_identity#Generalizations $\endgroup$ – BlueRaja - Danny Pflughoeft Aug 6 '10 at 21:40
  • $\begingroup$ Thanks, Qiaochu (& Pete & Bill & Danny et al.). I did not understand this before, but now I do! $\endgroup$ – Joseph O'Rourke Aug 7 '10 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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