Ecuación diofántica lineal

Una ecuación diofántica lineal (en dos variables) es una ecuación de la forma general:

$ax + by = c$

donde $a$ , $b$ , $c$ son enteros dados, y $x$ , $y$ son enteros desconocidos.

En este artículo consideramos varios problemas clásicos sobre estas ecuaciones:

encontrar una solución
encontrar todas las soluciones
encontrar la cantidad de soluciones y las soluciones mismas en un intervalo dado
encontrar una solución con valor mínimo de $x + y$

El caso degenerado

Un caso degenerado que hay que cuidar es cuando $a = b = 0$ . Es fácil ver que o no hay soluciones o hay infinitas, según si $c = 0$ o no. En el resto de este artículo ignoramos este caso.

Solución analítica

Cuando $a \neq 0$ y $b \neq 0$ , la ecuación $ax+by=c$ se puede tratar de forma equivalente como cualquiera de las siguientes:

$\begin{align} ax &\equiv c \pmod b \ by &\equiv c \pmod a \end{align}$

Sin pérdida de generalidad, supongamos que $b \neq 0$ y consideremos la primera ecuación. Cuando $a$ y $b$ son coprimos, la solución se da como

$x \equiv ca^{-1} \pmod b,$

donde $a^{-1}$ es el inverso modular de $a$ módulo $b$ .

Cuando $a$ y $b$ no son coprimos, los valores de $ax$ módulo $b$ para todo entero $x$ son divisibles por $g=\gcd(a, b)$ , así que la solución solo existe cuando $c$ es divisible por $g$ . En este caso, una de las soluciones se puede encontrar reduciendo la ecuación por $g$ :

$(a/g) x \equiv (c/g) \pmod{b/g}.$

Por definición de $g$ , los números $a/g$ y $b/g$ son coprimos, así que la solución se da explícitamente como

${\begin{cases} x \equiv (c / g) (a / g)^{- 1} (m o d b / g), \\ y = \frac{c - a x}{b} . \end{cases}$

Solución algorítmica

El lema de Bézout (también llamado identidad de Bézout) es un resultado útil para entender la siguiente solución.

Sea $g = \gcd(a,b)$ . Entonces existen enteros $x,y$ tales que $ax + by = g$ .

Además, $g$ es el menor entero positivo que se puede escribir como $ax + by$ ; todos los enteros de la forma $ax + by$ son múltiplos de $g$ .

Para encontrar una solución de la ecuación diofántica con 2 incógnitas, se puede usar el algoritmo de Euclides extendido. Primero, supongamos que $a$ y $b$ son no negativos. Cuando aplicamos el algoritmo de Euclides extendido a $a$ y $b$ , podemos encontrar su máximo común divisor $g$ y 2 números $x_g$ e $y_g$ tales que:

$a x_g + b y_g = g$

Si $c$ es divisible por $g = \gcd(a, b)$ , entonces la ecuación diofántica dada tiene solución; si no, no tiene ninguna. La demostración es directa: una combinación lineal de dos números es divisible por su divisor común.

Ahora supongamos que $c$ es divisible por $g$ , entonces tenemos:

$a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c$

Por lo tanto una de las soluciones de la ecuación diofántica es:

$x_0 = x_g \cdot \frac{c}{g},$

$y_0 = y_g \cdot \frac{c}{g}.$

La idea de arriba sigue funcionando cuando $a$ o $b$ o ambos son negativos. Solo hay que cambiar el signo de $x_0$ e $y_0$ cuando sea necesario.

Por último, podemos implementar esta idea así (nótese que este código no considera el caso $a = b = 0$ ):


int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

Obtener todas las soluciones

A partir de una solución $(x_0, y_0)$ , podemos obtener todas las soluciones de la ecuación dada.

Sea $g = \gcd(a, b)$ y sean $x_0, y_0$ enteros que satisfacen lo siguiente:

$a \cdot x_0 + b \cdot y_0 = c$

Ahora, deberíamos ver que sumar $b / g$ a $x_0$ y, al mismo tiempo, restar $a / g$ de $y_0$ no rompe la igualdad:

$a \cdot \left(x_0 + \frac{b}{g}\right) + b \cdot \left(y_0 - \frac{a}{g}\right) = a \cdot x_0 + b \cdot y_0 + a \cdot \frac{b}{g} - b \cdot \frac{a}{g} = c$

Obviamente, este proceso se puede repetir, así que todos los números de la forma:

$x = x_0 + k \cdot \frac{b}{g}$

$y = y_0 - k \cdot \frac{a}{g}$

son soluciones de la ecuación diofántica dada.

Como la ecuación es lineal, todas las soluciones yacen sobre la misma recta, y por definición de $g$ este es el conjunto de todas las soluciones posibles de la ecuación diofántica dada.

Encontrar la cantidad de soluciones y las soluciones en un intervalo dado

De la sección anterior debería quedar claro que si no imponemos restricciones sobre las soluciones, habría infinitas. Así que en esta sección añadimos restricciones sobre el intervalo de $x$ e $y$ , y vamos a intentar contar y enumerar todas las soluciones.

Sean dos intervalos: $[min_x; max_x]$ y $[min_y; max_y]$ y digamos que solo queremos encontrar las soluciones en estos dos intervalos.

Nótese que si $a$ o $b$ es $0$ , entonces el problema solo tiene una solución. No consideramos ese caso acá.

Primero, podemos encontrar una solución que tenga el valor mínimo de $x$ tal que $x \ge min_x$ . Para esto, primero encontramos cualquier solución de la ecuación diofántica. Después, desplazamos esta solución para obtener $x \ge min_x$ (usando lo que sabemos del conjunto de todas las soluciones en la sección anterior). Esto se puede hacer en $O(1)$ . Denotemos este valor mínimo de $x$ por $l_{x1}$ .

De forma similar, podemos encontrar el valor máximo de $x$ que satisface $x \le max_x$ . Denotemos este valor máximo de $x$ por $r_{x1}$ .

De forma similar, podemos encontrar el valor mínimo de $y$ $(y \ge min_y)$ y el valor máximo de $y$ $(y \le max_y)$ . Denotemos los valores correspondientes de $x$ por $l_{x2}$ y $r_{x2}$ .

La solución final son todas las soluciones con $x$ en la intersección de $[l_{x1}, r_{x1}]$ y $[l_{x2}, r_{x2}]$ . Denotemos esta intersección por $[l_x, r_x]$ .

A continuación está el código que implementa esta idea. Nótese que dividimos $a$ y $b$ al principio por $g$ . Como la ecuación $a x + b y = c$ es equivalente a $\frac{a}{g} x + \frac{b}{g} y = \frac{c}{g}$ , podemos usar esta última y tener $\gcd(\frac{a}{g}, \frac{b}{g}) = 1$ , lo que simplifica las fórmulas.


void shift_solution(int & x, int & y, int a, int b, int cnt) {
    x += cnt * b;
    y -= cnt * a;
}

int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
    int x, y, g;
    if (!find_any_solution(a, b, c, x, y, g))
        return 0;
    a /= g;
    b /= g;

    int sign_a = a > 0 ? +1 : -1;
    int sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (minx - x) / b);
    if (x < minx)
        shift_solution(x, y, a, b, sign_b);
    if (x > maxx)
        return 0;
    int lx1 = x;

    shift_solution(x, y, a, b, (maxx - x) / b);
    if (x > maxx)
        shift_solution(x, y, a, b, -sign_b);
    int rx1 = x;

    shift_solution(x, y, a, b, -(miny - y) / a);
    if (y < miny)
        shift_solution(x, y, a, b, -sign_a);
    if (y > maxy)
        return 0;
    int lx2 = x;

    shift_solution(x, y, a, b, -(maxy - y) / a);
    if (y > maxy)
        shift_solution(x, y, a, b, sign_a);
    int rx2 = x;

    if (lx2 > rx2)
        swap(lx2, rx2);
    int lx = max(lx1, lx2);
    int rx = min(rx1, rx2);

    if (lx > rx)
        return 0;
    return (rx - lx) / abs(b) + 1;
}

Una vez que tenemos $l_x$ y $r_x$ , también es simple enumerar todas las soluciones. Solo hay que iterar sobre $x = l_x + k \cdot \frac{b}{g}$ para todo $k \ge 0$ hasta $x = r_x$ , y encontrar los valores de $y$ correspondientes usando la ecuación $a x + b y = c$ .

Encontrar la solución con valor mínimo de { data-toc-label=‘Find the solution with minimum value of $x + y$ ’ }

Acá, $x$ e $y$ también necesitan alguna restricción; si no, la respuesta puede volverse menos infinito.

La idea es similar a la sección anterior: encontramos cualquier solución de la ecuación diofántica, y después desplazamos la solución para satisfacer algunas condiciones.

Por último, usamos el conocimiento del conjunto de todas las soluciones para encontrar el mínimo:

$x’ = x + k \cdot \frac{b}{g},$

$y’ = y - k \cdot \frac{a}{g}.$

Nótese que $x + y$ cambia así:

$x’ + y’ = x + y + k \cdot \left(\frac{b}{g} - \frac{a}{g}\right) = x + y + k \cdot \frac{b-a}{g}$

Si $a < b$ , hay que elegir el menor valor posible de $k$ . Si $a > b$ , hay que elegir el mayor valor posible de $k$ . Si $a = b$ , todas las soluciones tendrán la misma suma $x + y$ .