---
tags: number-theory, gcd, lcm, euclidean-algorithm, extended-euclidean-algorithm, diophantine-equations
---

# Algoritmo de Euclides
Sean $a$ y $b$ dos enteros. Si enlistamos todos los divisores positivos de ambos, tomamos la intersección y nos quedamos con el máximo, estaremos obteniendo el *máximo común divisor* de $a$ y $b$, usualmente denotado como $\gcd(a,b)$.

:::info
:information_source: **Ejemplo:** $\gcd(30,75)=15$, pues los divisores del $30$ son $\{\color{red}{1},2,\color{red}{3},\color{red}{5},6,10,\color{red}{15},30\}$, los divisores del $75$ son $\{\color{red}{1},\color{red}{3},\color{red}{5},\color{red}{15},25,75\}$, los comunes son $\{\color{red}{1},\color{red}{3},\color{red}{5},\color{red}{15}\}$ y el mayor de ellos es el $\boxed{\color{red}{15}}$.
:::

Vemos que el $1$ siempre estará en la intersección sin importar quiénes sean $a$ y $b$, entonces el $\gcd(a,b)$ siempre será al menos $1$. Si $\gcd(a,b) = 1$, diremos que $a$ y $b$ son *coprimos* o *primos relativos*, pues no comparten ningún divisor no trivial.

## Definición formal

Ahora daremos una definición formal del máximo común divisor: si $d$ es un entero positivo que cumple las siguientes dos propiedades propiedades:
- **Divisor común:** $d \mid a$ y $d \mid b$.
- **Maximalidad:** si existe un entero positivo $c$ tal que $c \mid a$ y $c \mid b$, entonces $c \mid d$.

entoces diremos que $d = \gcd(a,b)$. Dicha definición nos ayudará a demostrar propiedades para el gcd y proponer un algoritmo eficiente para calcularlo.

:::info
:information_source: **Ejemplo:** volvamos al ejemplo de $\gcd(30,75)$ y veamos que $d=15$ tiene que ser el máximo común divisor de $30$ y $75$ con base en la definición anterior.

Para cumplir la primer propiedad requerimos encontrar un divisor $d$ común de $30$ y $75$, y habíamos visto que los candidatos eran $\{1,3,5,15\}$.

La segunda propiedad es la más interesante, pues no importa qué divisor $c$ común escogamos, ese siempre tiene que dividir a $d$. Veamos:
- Si escogemos $d=15$, no importa qué divisor común $c$ escojamos, ese siempre dividirá al $15$: $1 \mid 15$, $3 \mid 15$, $5 \mid 15$, $15 \mid 15$.
- Si escogemos, por ejemplo, $d=5$, podríamos tomar $c=3$, pero $3 \not \mid 5$, por lo tanto $5$ no cumple con ser el máximo.
- Lo mismo pasa si escogemos $d=3$ o $d=1$.

Por lo tanto, la segunda propiedad garantiza que el candidato $d$ al máximo común divisor sea máximo, ya que todos los divisores comunes $c$ no necesariamente máximos tienen que estar *contenidos* el $d$, garantizando que $d$ contenga a todos.
:::

### Propiedades

Tenemos las siguientes propiedades:
- **Conmutativo:** $\gcd(a,b) = \gcd(b,a)$
- **El signo no importa:** $\gcd(a,b) = \gcd(\lvert a \rvert, \lvert b \rvert)$
- $\gcd(a,0) = \lvert a \rvert$
- $\gcd(0,0)$ usualmente no está definido.
- Si $b \mid a$, entonces $\gcd(a,b)=b$
- $\gcd(ma, mb) = \lvert m \rvert \gcd(a,b)$
- Si $d=\gcd(a,b)$, entonces $\gcd(a/d,b/d)=1$
- $\gcd(a, a+1) = 1$
- **Asociativo:** Podemos extender la definición y calcular el gcd de tres números: $\gcd(a,b,c) = \gcd(\gcd(a,b),c)$. En general, para hallar el gcd de $n$ números, los tomamos de dos en dos y vamos reduciendo hasta que nos queden dos.

Y la propiedad suprema: sean $q,r$ enteros tales que $a=bq+r$, entonces $\gcd(a,b)=\gcd(b,r)$.

:::info
:information_source: **Ejemplo:** una forma de interpretar la propiedad anterior es que podemos restarle a $a$ cualquier múltiplo de $b$, y eso no va a afectar el gcd. Si volvemos a tomar $a=75$ y $b=30$, entonces:
- Si $q=1$, le restamos $b$ a $a$ una vez: $\gcd(75,30) = \gcd(75-30,30) = \gcd(45,30) = 15$
- Si $q=2$, le restamos $b$ a $a$ dos veces: $\gcd(75,30) = \gcd(75-2 \times 30, 30) = \gcd(15,30)=15$
:::

:::spoiler **Demostración**
Sea $d=\gcd(a,b)$, demostremos que también $d=\gcd(b,r)$ al verificar las dos propiedades de la definición:
- Queremos demostrar que $d \mid b$ y $d \mid r$. Ya sabemos que $d \mid b$ pero también $d \mid a$, entonces $d$ dividirá también a cualquier combinación lineal de $b$ y $a$, en particular a $(1)a+(-q)b$ que es justamente $r$, por lo tanto $d \mid r$.
- Sea $c$ un entero tal que $c \mid b$ y $c \mid r$, queremos demostrar que $c \mid d$. De nuevo, $c$ dividirá a cualquier combinación lineal de $b$ y $r$, en particular a $(q)b+(1)r$ que es justamente $a$, por lo tanto $c \mid a$. Pero como $d$ es el máximo común divisor de $a$ y $b$, y $c \mid a$ y $c \mid b$, entonces $c \mid d$.
:::

Esta propiedad la podemos explotar al máximo de las siguientes dos formas:
- La propiedad no impone restricciones adicionales en $q$ y en $r$, entonces al escoger $q$ y $r$ tales que sean el cociente y el residuo de $a$ con $b$ respectivamente, es decir, $q=\lfloor a/b \rfloor$ y $r = a\%b$, estamos maximizando el número de veces que le restamos $b$ a $a$, teniendo números más pequeños en cada paso.
- Si la aplicamos de forma repetida hasta que lleguemos a un punto de la forma $\gcd(a,0)$ ya habremos terminado, pues $\gcd(a,0) = \lvert a \rvert$.

Y a dicho algoritmo se le conoce como el *Algoritmo de Euclides*.

:::info
:information_source: **Ejemplos:**
- $\gcd(75, 30) = \gcd(30, \underbrace{15}_{75 \% 30}) = \gcd(15, \underbrace{0}_{30 \% 15}) = 15$
- $\gcd(16, 42) = \gcd(42, \underbrace{16}_{16 \% 42}) = \gcd(16, \underbrace{10}_{42 \% 16}) = \gcd(10, \underbrace{6}_{16 \% 10}) = \gcd(6, \underbrace{4}_{10 \% 6}) = \gcd(4, \underbrace{2}_{6 \% 4}) = \gcd(2, \underbrace{0}_{4 \% 2}) = 2$
:::

Por lo tanto, tenemos que:
$$
\gcd(a, b) = \begin{cases}
\gcd(b, a \% b) &\mbox{si $b \neq 0$} \\
\lvert a \rvert &\mbox{si $b=0$}
\end{cases}
$$

Para implementar la fórmula, hacerlo de forma recursiva es muy natural:
### Algoritmo 1: Algoritmo de Euclides

int gcd(int a, int b){
    if(b == 0){
        return abs(a);
    }else{
        return gcd(b, a%b);
    }
}

Analicemos la complejidad:
- Primero veamos que el algoritmo termina y no se cicla: asumiendo que $a \geq b \geq 0$, el segundo argumento de la función es estrictamente decreciente, pues $0 \leq r < b$ y por eso en algún momento llegará a cero. Si $a < b$ no pasa nada, pues se intercambian en la primera iteración.
- El peor caso es cuando $q=1$ en cada caso, es decir, le estamos restando $b$ a $a$ solo una vez. Para lograr este caso, el algoritmo tiene que recibir como entrada dos números consecutivos de la sucesión de Fibonacci: $a=F_n$ y $b=F_{n-1}$, logrando $n-2$ llamadas recursivas. Como los números de Fibonacci crecen exponencialmente, la complejidad del peor caso es $O(\log \min(a,b))$.
- El algoritmo sigue funcioanndo correctamente aunque C++ calcule mal el residuo de $a$ con $b$ si alguno de los dos es negativo, pues la condición $a=bq+r$ se sigue cumpliendo y no hay restricciones adicionales en $q$ y en $r$.

:::success
:heavy_check_mark: En C++ ya existe la función que implementa el algoritmo de Euclides: ``__gcd(a, b)``.
:::

### Obtener el gcd a través de la factorización
Si tenemos $a$ y $b$ dados por su factorización en primos, existe una forma alternativa de calcular $\gcd(a, b)$:
- Supongamos que $a$ y $b$ son potencias del mismo primo $p$, es decir, $a=p^u$ y $b=p^v$. Entonces $\gcd(a,b)=p^{\min(u,v)}$, pues tanto $u-\min(u,v)$ como $v-\min(u,v)$ son enteros no negativos, lo que garantiza que $p^{\min(u,v)} \mid p^u$ y $p^{\min(u,v)} \mid p^v$. Además es fácil ver que $p^{\min(u,v)}$ es el máximo, pues al menos uno de $u-\min(u,v)$ y $v-\min(u,v)$ es cero, y si aumentamos en $1$ el exponente, ya no se cumple la propiedad de divisibilidad.
- Si $a$ y $b$ son números cualquiera, consideramos cada primo en la unión de todos los factores primos de $a$ y $b$, hacemos el paso anterior por cada uno de ellos y multiplicamos los resultados.

:::info
:information_source: **Ejemplo:** sabemos que $75 = 3 \times 5^2$ y que $30 = 2 \times 3 \times 5$. Todos los primos involucrados son $\{2,3,5\}$, analicemos cada uno:
- El exponente del $2$ en $75$ es $0$ y en $30$ es $1$, por lo tanto este primo aporta $2^{\min(0,1)}=2^0=1$ al gcd.
- El exponente del $3$ en $75$ es $1$ y en $30$ es $1$, por lo tanto este primo aporta $3^{\min(1,1)} = 3^1 = 3$ al gcd.
- El exponente del $5$ en $75$ es $2$ y en $30$ es $1$, por lo tanto este primo aporta $5^{\min(2,1)} = 5^1 = 5$ al gcd.

Por lo tanto, $\gcd(75,30) = 1 \times 3 \times 5 = 15$.
:::

Este método también se puede generalizar cuando queremos hallar el gcd de tres o más números, simplemente tomamos el mínimo de todos los exponentes de cada número por cada primo.

## Mínimo común múltiplo
Sean $a$ y $b$ dos enteros positivos. Si enlistamos todos los múltiplos positivos de ambos números y tomamos el mínimo en común, ese será el mínimo común múltiplo de $a$ y $b$, y escribimos $\text{lcm}(a,b)$.

:::info
:information_source: **Ejemplo:** calculemos $\text{lcm}(75,30)$;
- Los primeros múltiplos de $75$ son: $75, \color{red}{150}, 225, \color{blue}{300}, 375, 450. \ldots$
- Los primeros múltiplos de $30$ son: $30, 60, 90, 120, \color{red}{150}, 180, 210, 240, 270, \color{blue}{300}, 330, \ldots$

Vemos que los múltiplos en común son $150, 300, 450, \ldots$ y el más chico es $150$, por lo tanto $\text{lcm}(75,30)=150$.
:::

Para hallarlo de forma eficiente, notemos que debemos hallar $s, t \in \mathbb{N}$ mínimos tales que $as = bt$, reacomodamos y obtenemos $\frac{a}{b}=\frac{t}{s}$. Para simplificar al máximo la fracción $\frac{a}{b}$ dividimos arriba y abajo entre $\gcd(a,b)$, es decir, $\frac{a/\gcd(a,b)}{b/\gcd(a,b)}=\frac{t}{s}$. Como $s$ y $t$ son mínimos y la fracción ya quedó reducida al mínimo, forzosamente se cumple que $s=\frac{b}{\gcd(a,b)}$ y $t=\frac{a}{\gcd(a,b)}$. Finalmente, $\text{lcm}(a,b) = as = a \cdot \frac{b}{\gcd(a,b)}$, o equivalentemente, $\text{lcm}(a,b) = bt = b \cdot \frac{a}{\gcd(a,b)}$. En ambos casos tenemos la fórmula:
$$
\text{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}
$$

Y la implementación queda trivial:

### Algoritmo 2: Mínimo común múltiplo

int lcm(int a, int b){
    return a / gcd(a,b) * b; // Primero dividimos entre el gcd y luego multiplicamos para evitar un desbordamiento
}

Si $a$ o $b$ son negativos, simplemente agregamos valor absoluto a la fórmula anterior.

### Propiedades
El lcm cumple lo siguiente:
- **Conmutativo:** $\text{lcm}(a,b) = \text{lcm}(b,a)$
- $\text{lcm}(ma, mb) = \lvert m \rvert \text{lcm}(a,b)$
- Si $a$ y $b$ son coprimos, entonces $\text{lcm}(a,b) = ab$
- $\text{lcm(a, 1)} = \lvert a \rvert$
- **Asociativo:** Podemos extender la definición y calcular el lcm de tres números: $\text{lcm}(a,b,c) = \text{lcm}(\text{lcm}(a,b),c)$. En general, para hallar el lcm de $n$ números, los tomamos de dos en dos y vamos reduciendo hasta que nos queden dos.
- **Distributivo:**
- $\text{lcm}(k, \gcd(c_1, c_2, \ldots, c_n)) = \gcd(\text{lcm}(k, c_1), \text{lcm}(k, c_2), \ldots, \text{lcm}(k, c_n))$
- $\gcd(k, \text{lcm}(c_1, c_2, \ldots, c_n)) = \text{lcm}(\gcd(k, c_1), \gcd(k, c_2), \ldots, \gcd(k, c_n))$

### Obtener el lcm a través de la factorización
Si tenemos $a$ y $b$ dados por su factorización en primos, existe una forma alternativa de calcular $\text{lcm}(a, b)$:
- Supongamos que $a$ y $b$ son potencias del mismo primo $p$, es decir, $a=p^u$ y $b=p^v$. Entonces $\text{lcm}(a,b)=p^{\max(u,v)}$, pues $\text{lcm}(a,b) = \frac{ab}{\gcd(a,b)} = \frac{p^{u+v}}{p^{\min(u,v)}} = p^{u+v-\min(u,v)} = p^{\max(u,v)}$.
- Si $a$ y $b$ son números cualquiera, consideramos cada primo en la unión de todos los factores primos de $a$ y $b$, hacemos el paso anterior por cada uno de ellos y multiplicamos los resultados.

:::info
:information_source: **Ejemplo:** sabemos que $75 = 3 \times 5^2$ y que $30 = 2 \times 3 \times 5$. Todos los primos involucrados son $\{2,3,5\}$, analicemos cada uno:
- El exponente del $2$ en $75$ es $0$ y en $30$ es $1$, por lo tanto este primo aporta $2^{\max(0,1)}=2^1=2$ al lcm.
- El exponente del $3$ en $75$ es $1$ y en $30$ es $1$, por lo tanto este primo aporta $3^{\max(1,1)} = 3^1 = 3$ al lcm.
- El exponente del $5$ en $75$ es $2$ y en $30$ es $1$, por lo tanto este primo aporta $5^{\max(2,1)} = 5^2 = 25$ al lcm.

Por lo tanto, $\text{lcm}(75,30) = 2 \times 3 \times 25 = 150$.
:::

Este método también se puede generalizar cuando queremos hallar el lcm de tres o más números, simplemente tomamos el máximo de todos los exponentes de cada número por cada primo.

## Algoritmo de Euclides extendido
Sean $a, b \in \mathbb{Z}$. Consideremos todas sus combinaciones lineales $ax+by$, ¿cuál es el mínimo valor positivo que podemos obtener? Sea $d = \gcd(a,b)$, entonces $d$ siempre estará garantizado a dividir a $ax+by$ y $d$ es el máximo número con esta propiedad, lo que implica que dichas combinaciones lineales siempre serán múltiplos de $d$, por lo que el mínimo valor de $ax+by$ es $d$ (identidad de Bezout). Ahora la pregunta es, ¿cómo hallar $x$ y $y$ tales que $ax+by=\gcd(a,b)$?

:::info
:information_source: **Ejemplo:** Para $a=75$ y $b=30$, algunas combinaciones lineales que podemos obtener son:
- $75(1) + 30(1) = 105$
- $75(1) + 30(2) = 135$
- $75(2) + 30(1) = 180$
- $75(-1) + 30(3) = 15$

Vemos que todos esos números son múltiplos de $15$ y de hecho encontramos por ensayo y error que $x=-1$ y $y=3$ produce la combinación lineal igual a $\gcd(75,30)$.
:::

Modifiquemos el algoritmo de Euclides para que en la transición $(a,b) \to (b,r)$ obtengamos $x, y$ tales que $ax+by=d$. Supongamos que ya conocemos $x_{old}, y_{old}$ de la iteración pasada tales que $bx_{old} + ry_{old} = d$ y queremos actualizarlos en esta iteración para obtener $x_{new}, y_{new}$ tales que $ax_{new} + by_{new} = d$.

Sabemos que $r=a-bq$, entonces lo podemos sustituir:
$$
bx_{old} + (a-bq)y_{old} = d
$$
Ahora reacomodemos tal que se vea la nueva combinación lineal de $a$ y $b$:
$$
\begin{align}
bx_{old} + ay_{old} - bqy_{old} &= d \\
a\underbrace{y_{old}}_{x_{new}} + b(\underbrace{x_{old} - qy_{old}}_{y_{new}}) &= d
\end{align}
$$

Comparando, tenemos que $(x_{new}, y_{new}) \gets (y_{old}, x_{old} - qy_{old})$.

Solo queda ver en el caso base qué combinación lineal nos sirve, es decir, cuando $b=0$:
- Si $a > 0$, entonces $d=a$ y $a(\underbrace{1}_{x}) + 0(\underbrace{0}_{y}) = \underbrace{a}_{d}$, por lo tanto $(x,y)=(1,0)$.
- Si $a < 0$, entonces $d=-a$ y $a(\underbrace{-1}_{x})+0(\underbrace{0}_{y})=\underbrace{-a}_{d}$, por lo tanto $(x,y)=(-1,0)$.

Notemos que en ambos casos pudimos haber tomado cualquier valor entero para $y$, pero por simplicidad tomamos $y=0$.

Veamos un ejemplo y luego la implementación:
:::info
:information_source: **Ejemplo:** Hallemos $x,y$ tales que $42x+16y=\gcd(42,16)$. El algoritmo calculará de arriba hacia abajo las columnas $a,b$, y llegando al caso base, cada que una llamada recursiva termine irá calculando $x,y$ de abajo hacia arriba. Entonces, la tabla se puede leer en forma de "U":

$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\text{# Llamada recursiva} & a & b & q & r & x & y & \text{Comprobación} \\
\hline
1^\circ & 42 & 16 & 2 & 10 & \boxed{\color{magenta}{-3}} & \color{purple}{2} - 2(\color{magenta}{-3}) = \boxed{\color{gray}{8}} & 42(\color{magenta}{-3}) + 16(\color{gray}{8}) = 2 \\
\hline
2^\circ & 16 & 10 & 1 & 6 & \color{purple}{2} & \color{green}{-1} - 1(\color{purple}{2}) = \color{magenta}{-3} & 16(\color{purple}{2}) + 10(\color{magenta}{-3}) = 2 \\
\hline
3^\circ & 10 & 6 & 1 & 4 & \color{green}{-1} & \color{orange}{1} - 1(\color{green}{-1}) = \color{purple}{2} & 10(\color{green}{-1}) + 6(\color{purple}{2}) = 2 \\
\hline
4^\circ & 6 & 4 & 1 & 2 & \color{orange}{1} & \color{blue}{0} - 1(\color{orange}{1}) = \color{green}{-1} & 6(\color{orange}{1}) + 4(\color{green}{-1}) = 2 \\
\hline
5^\circ & 4 & 2 & 2 & 0 & \color{blue}{0} & \color{red}{1} - 2(\color{blue}{0}) = \color{orange}{1} & 4(\color{blue}{0}) + 2(\color{orange}{1}) = 2 \\
\hline
6^\circ & \boxed{2} & 0 & - & - & \color{red}{1} & \color{blue}{0} & 2(\color{red}{1}) + 0(\color{blue}{0}) = 2 \\
\hline
\end{array}
$$

Por lo tanto, $\gcd(42,16)=2$, $x=-3$ y $y=8$. También podemos visualizar los pasos así:
$$
\begin{alignat}{2}
(a,b) &= (42, 16) \to (16, 10) \to (10, 6) \to (6, 4) \to (4, 2) \to (2, 0) &\searrow \\
(x,y) &= (\color{magenta}{-3}, \color{gray}{8}) \gets (\color{purple}{2}, \color{magenta}{-3}) \gets (\color{green}{-1}, \color{purple}{2}) \gets (\color{orange}{1}, \color{green}{-1}) \gets (\color{blue}{0}, \color{orange}{1}) \gets (\color{red}{1}, \color{blue}{0}) &\swarrow
\end{alignat}
$$
:::

Para implementarlo, vamos a programar una función llamada ``extgcd`` que reciba $a$ y $b$, y devuelva una tupla de tres valores $(\gcd(a,b), x, y)$:

### Algoritmo 3: algoritmo extendido de Euclides

tuple<int,int,int> extgcd(int a, int b){
    if(b == 0){
        if(a > 0) return {a, 1, 0};
        else return {-a, -1, 0};
    }else{
        auto[d, x, y] = extgcd(b, a%b); // Solo funciona a partir de C++17, la siguiente línea funciona desde C++11
        // int d, x, y; tie(d, x, y) = extgcd(b, a%b);
        return {d, y, x - (a/b)*y};
    }
}

Una forma alternativa de implementación es que la función solo devuelva el $\gcd(a,b)$ y que reciba a $x$ y a $y$ por referencia para modificarlos. También podemos realizar la implementación de forma iterativa, tanto de la versión normal como de la extendida.

La complejidad del algoritmo extendido sigue siendo la misma del algoritmo normal de Euclides, pues solo agregamos operaciones constantes.

Una observación importante es que si $a$ y $b$ caben dentro de un tipo de dato con signo, entonces $x$ y $y$ también lo harán dentro de ese mismo tipo de dato y no habrá desbordamientos intermedios. Otra es que el par $(x,y)$ obtenido por este algoritmo siempre será el mínimo en valor absoluto, es decir, se minimiza $\lvert x \rvert + \lvert y \rvert$.

### Familia de soluciones
En los ejemplos anteriores vimos que $75(-1) + 30(3) = \gcd(75, 30) = 15$, pero si corremos el algoritmo anterior obtenemos $75(1) + 30(-2) = 15$, la cual también es una combinación válida. En general, para cualesquiera $a$ y $b$, siempre habrá infinitos pares $(x,y)$ que cumplan $ax+by=\gcd(a,b)$. Veamos cómo obtenerlos todos:

Supongamos que el algoritmo extendido de Euclides nos devolvió la tupla $(d, x_0, y_0)$ tal que $ax_0 + by_0 = d = \gcd(a,b)$. Llamaremos al par $(x_0, y_0)$ la *solución base* y asumiremos que cualquier solución $(x,y)$ de $ax+by=d$ puede ser parametrizada como:
$$
\begin{cases}
x = x_0 + sk \\
y = y_0 + tk
\end{cases}
$$
donde $k \in \mathbb{Z}$ es el parámetro y $s,t$ son enteros a determinar. Si sustituimos, obtenemos $a(x_0+sk) + b(y_0+tk) = d$, que queda $ax_0 + ask + by_0 + btk = d$ y se simplifica a $(as+bt)k=0$. Como $k$ puede ser cualquier entero, entonces $as+bt=0$. Reacomodamos y queda $\frac{-a}{b} = \frac{t}{s}$. Podemos volver a aplicar el truco de reducir al máximo la fracción $\frac{a}{b}$ al dividir arriba y abajo entre su gcd, y queda: $t=-\frac{a}{d}$, $s=\frac{b}{d}$, y la familia de soluciones es entonces:
$$
\begin{cases}
x = x_0 + \frac{b}{d} \cdot k \\
y = y_0 - \frac{a}{d} \cdot k
\end{cases}
$$

Ya demostramos que la familia de soluciones que propusimos siempre satisface la ecuación $ax+by=d$, pero, ¿realmente obtendremos TODAS las soluciones con dicha parametrización? La respuesta es SÍ, y para demostrarlo, supongamos que tenemos dos soluciones $(x_1, y_1)$ y $(x_2, y_2)$ a la ecuación $ax+by=d$, es decir, $ax_1 + by_1 = d$ y $ax_2 + by_2 = d$. Restamos ambas ecuaciones y obtenemos $a(x_1-x_2) + b(y_1-y_2) = 0$. Reacomodamos: $\frac{-a}{b} = \frac{y_1-y_2}{x_1-x_2}$ y de nuevo reducimos al máximo: $\frac{-a/d}{b/d} = \frac{y_1-y_2}{x_1-x_2}$, de donde se ve que $\frac{b}{d} \mid (x_1-x_2)$ y $\frac{a}{d} \mid (y_1-y_2)$, lo que nos quiere decir que la diferencia en $x$ de dos soluciones es divisible entre $\frac{b}{d}$ y la diferencia en $y$ es divisible entre $\frac{a}{d}$, lo cual siempre se cumple con la familia de soluciones propuesta.

:::info
:information_source: **Ejemplo:** si $a=42$ y $b=16$ como en el último ejemplo, obtuvimos que $(x_0, y_0) = (-3, 8)$ y $d=2$. Entonces, la familia de soluciones de $42x+16y=2$ es:
$$
\begin{cases}
x = -3 + \frac{16}{2}k = -3 + 8k \\
y = 8 - \frac{42}{2}k = 8 - 21k
\end{cases}
$$
Generemos algunas:
- $\cdots$
- $k=-2 \implies (x,y) = (-3+8(-2), 8-21(-2)) = (-19, 50)$
- $k=-1 \implies (x,y) = (-3+8(-1), 8-21(-1)) = (-11, 29)$
- $k=0 \implies (x,y) = (-3, 8)$
- $k=1 \implies (x,y) = (-3+8(1), 8-21(1)) = (5, -13)$
- $k=2 \implies (x,y) = (-3+8(2), 8-21(2)) = (13, -34)$
- $\cdots$
:::

## Ecuaciones diofánticas
Sean $a,b,c \in \mathbb{Z}$, queremos hallar todas las soluciones enteras $(x,y)$ de la ecuación $ax+by=c$. Veamos cómo reusar lo que ya sabemos de la sección anterior.

Si corremos el algoritmo extendido de Euclides con la entrada $(a,b)$, obtendremos la salida $(d,x_0,y_0)$ tal que $ax_0+by_0=\gcd(a,b)=d$. ¿Cómo podemos transformar esa igualdad a la ecuación que queremos resolver? Vemos que lo que cambia es el lado derecho, en la ecuación que queremos resolver tenemos $c$ y en la igualdad que ya sabemos tenemos $d$. Por lo tanto, podemos multiplicar ambos lados de la igualdad por $\frac{c}{d}$ y así cambiar $d$ por $c$:
$$
\begin{align}
(ax_0 + by_0) \frac{c}{d} &= d \cdot \frac{c}{d} \\
a \cdot \left( x_0 \cdot \frac{c}{d} \right) + b \cdot \left( y_0 \cdot \frac{c}{d} \right) &= c
\end{align}
$$

De ahí vemos claramente que la solución base para nuestra ecuación diofántica original es $\left( x_0 \cdot \frac{c}{d}, y_0 \cdot \frac{c}{d} \right)$. Por supuesto que requerimos que $d \mid c$, pues en caso contrario no hay soluciones. Esto tiene sentido, pues sabemos que cualquier combinación lineal de $a$ y $b$ tiene que ser múltiplo de $d$, por lo que para que la ecuación original sea resolvible, $c$ tiene que ser múltiplo de $d$.

Y de forma similar, también existirá una familia de soluciones para la ecuación diofántica, que es:
$$
\begin{cases}
x = x_0 \cdot \frac{c}{d} + \frac{b}{d} \cdot k \\
y = y_0 \cdot \frac{c}{d} - \frac{a}{d} \cdot k
\end{cases}
$$
para cualquier $k \in \mathbb{Z}$.

:::info
:information_source: **Ejemplo:** Resolvamos la ecuación $42x+16y=18$. Por el algoritmo extendido de Euclides sabemos que $(x_0,y_0)=(-3,8)$ y $d=2$. Como $2 \mid 18$, existen infinidad de soluciones, y están dadas por:
$$
\begin{cases}
x = -3 \cdot \frac{18}{2} + \frac{16}{2} \cdot k = -27 + 8k \\
y = 8 \cdot \frac{18}{2} - \frac{42}{2} \cdot k = 72 - 21k
\end{cases}
$$
Generemos algunas:
- $\cdots$
- $k=-2 \implies (x,y) = (-27+8(-2), 72-21(-2)) = (-43, 114)$
- $k=-1 \implies (x,y) = (-27+8(-1), 72-21(-1)) = (-35, 93)$
- $k=0 \implies (x,y) = (-27, 72)$
- $k=1 \implies (x,y) = (-27+8(1), 72-21(1)) = (-19, 51)$
- $k=2 \implies (x,y) = (-27+8(2), 72-21(2)) = (-11, 30)$
- $\cdots$
:::