Yo necesitaba (para mi investigación) para resolver una ecuación de Diophantine, en particular, $$ 2 a + 3 b + 4 c + 5 d = 12 .$$ Y yo podría solucionarlo (por ejemplo, en la solución de es $a=2, b=1, c=0, d=1$). Pero esto me hizo preguntarme si tales ecuaciones, con sus coeficientes de aumento de las secuencias de números naturales, son un caso especial de Diophantine ecuaciones que son siempre explícitamente solucionable, a pesar de la negativa de la solución a Hilbert 10 del problema.
Respuesta
¿Demasiados anuncios?
Lineal Diophantine ecuaciones son siempre solucionable decidable (en el tiempo lineal). Si los coeficientes se $a_1, a_2, ... a_n$, entonces los números que aparecen en la RHS son precisamente los múltiplos de $\text{gcd}(a_1, ... a_n)$, y uno puede encontrar soluciones mediante el algoritmo de Euclides extendido.
