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.
Diophantine equations whose coefficients are increasing sequences of integers
4
$\begingroup$
number-theory
diophantine-equations
-
0as long as some of the coefficents are relatively prime, we can use bezouts identity. – 2010-08-06
-
0@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? – 2010-08-06
-
0If they are relatively prime you can solve for any number, but if they are not you can only hit multiples of the GCD. – 2010-08-06
-
3BTW, 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](http://mathworld.wolfram.com/FrobeniusNumber.html) or [coin problem](http://en.wikipedia.org/wiki/Coin_problem). – 2010-08-06
-
1dividing 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
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.
-
3+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. – 2010-08-06
-
0See also: http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity#Generalizations – 2010-08-06
-
0Thanks, Qiaochu (& Pete & Bill & Danny et al.). I did not understand this before, but now I do! – 2010-08-07