OIA-Wiki

Las ecuaciones diofánticas lineales son las expresiones $A*x + B*y = C$, donde $A, B, C$ son números enteros dados, y $x, y$ son las variables enteras que hay que encontrar. El lema llamado “Lema de Bézout” afirma que el sistema tiene solución si y sólo si $d = mcd(A, B)$ divide a $C$. Esto suele verse como que el menor número positivo $C$ para el cual existe solución es $C=mcd(A, B)$. Y a partir de ahí, si tenemos $(x,y)$ tales que $A*x + B*y = d$, y $C=k*d$, luego $A*x*k + B*y*k = d*k = C$, y tendremos que $(x*k, y*k)$ será solución del sistema inicial.

Entonces a partir de ahora vamos a tratar el problema $A*x + B*y = mcd(A, B) = d$, y luego sabemos como llevar las soluciones de este sistema a las de uno con $C=k*d$ para cualquier $k$ entero.

Veamos que si existe solución, existen infinitas soluciones:

Supongamos que tenemos $(x,y)$ solución del sistema. Sea $k$ un entero cualquiera, veamos que $(x+k*\frac{B}{mcd(A,B)}, y-k*\frac{A}{mcd(A,B)})$ es solución:

$ A*(x+k*\frac{B}{mcd(A,B)}) + B*(y-k*\frac{A}{mcd(A,B)}) = $ $A*x + A*k*\frac{B}{mcd(A,B)} + B*y - B*k*\frac{A}{mcd(A,B)} = A*x + B*y = d $

Como esto se cumple para cualquier $k$ entero, hay infinitas soluciones.

Esto de encontrar soluciones a partir de otras es súper útil, porque hay problemas que podemos necesitar una solución en la que ambas $x$ e $y$ sean positivas, como por ejemplo si quisiéramos pagar un precio $d$ con monedas de valores $A$ y $B$, usando por lo menos una moneda de cada valor. En ese caso, puede que nuestro algoritmo encuentre una solución con alguno de los valores negativos, pero luego usamos esta fórmula para buscar (si es que existe) una solución con ambos valores positivos.

Para encontrar una solución, se aprovecha el algoritmo de Euclides mencionado en el post de MCD.

Supongamos que $A = B*q_1 + r_1$. Luego, debemos calcular $mcd(B, r_1)$: $B = r_1*q_2 + r_2$ $r_1 = r_2*q_3 + r_3$ $\ldots$ $r_{t-3} = r_{t-2}*q_{t-1} + r_{t-1}$ $r_{t-2} = r_{t-1}*q_{t} + r_{t}$ $r_{t-1} = r_t*q_{t+1}$

Acá, $r_t = mcd(A,B) = d$. Una vez llegado al final, vamos reconstruyendo: $r_{t-2}-r_{t-1}*q_t = d$

Substituyendo de la antepenúltima ecuación el valor de $r_{t-1}$: $r_{t-2} - (r_{t-3} - r_{t-2}*q_{t-1})*q_t = d$

Y así seguimos, recursivamente, hasta encontrar los valores de $x$ e $y$.

El mejor código que conozco de esto y que voy a transcribir acá es de una clase de Pablo Blanc dictada en el Training Camp 2017, en la parte en la que habla de MCD. Usa struct, que se puede leer acá.

Hay muchos códigos en internet para resolver este tipo de ecuaciones pero la mayoría usa punteros (algo que ni siquiera es tan necesario de saber).

struct dxy {
    long long int d,x,y;
};
 
dxy mcde(long long int a, long long int b) {
    dxy r, t;
    if (b == 0) {
        r.d = a;
        r.x = 1;
        r.y = 0;
    } else {
        t = mcde(b, a%b);
        r.d = t.d;
        r.x = t.y;
        r.y = t.x - a/b*t.y;
    }
    return r;
}

Así, entonces, haciendo

dxy ans = mcde(20, 35);
cout<<"20*("<<ans.x<<") + 35*("<<ans.y<<") = "<<ans.d<<endl;

obtenemos: 20*(2) + 35*(-1) = 5, donde $5$ es $mcd(20, 35)$.