4
$\begingroup$

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.

  • 1
    dividing through by the gcd of the coefs reduces to the case where they have gcd = 1, where you can apply Bezout.2010-08-06

1 Answers 1

8

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.

  • 0
    Thanks, Qiaochu (& Pete & Bill & Danny et al.). I did not understand this before, but now I do!2010-08-07