Cómo encontrar una solución entera para la ecuación general de Diofantina ax + por + cz + dt... = N

Question

Sé cómo resolver ax + by = c usando el Algoritmo Extendido. Pero con más que variables, estoy perdido. Verificar si tiene una solución entera es fácil, ya que sólo tenemos que comprobar si hay gcd(a,b,c)|d. Aparte de eso, ¿cómo podemos encontrar una solución entera para esta ecuación?

Gracias,
Chan

Answer 1

Supongamos que necesitas resolver $$a_1x_1 + a_2x_2 + a_3x_3 = c \qquad (1)$$ en números enteros.

Afirmo que esto equivale a resolver $$ \gcd (a_1,a_2)y + a_3x_3 = c \qquad (2)$$ en números enteros.

Para ver esto, note que cualquier solución a (1) produce una solución a (2): dejar $g= \gcd (a_1,a_2)$ podemos escribir $a_1 = gk_1$ , $a_2=gk_2$ así que lo hemos hecho: $$c = a_1x_1 + x_2x_2 + a_3x_3 = g(k_1x_1) + g(k_2x_2) + a_3x_3 = g(k_1x_1+k_2x_2) + a_3x_3,$$ resolviendo (2). A la inversa, supongamos que tienes una solución para (2). Ya que podemos encontrar $r$ y $s$ de tal manera que $g=ra_1+sa_2$ Tenemos $$c = gy+a_3x_3 = (ra_1+sa_2)y +a_3x_3 = a_1(ry) + a_2(sy) + a_3x_3,$$ dando una solución a (1).

Esto debería decirle cómo resolver el caso general $$a_1x_1+ \cdots +a_nx_n = c$$ en términos de $ \gcd (a_1, \ldots ,a_n)$ que a su vez puede ser computado recursivamente.