Algoritmo de Euclides e identidad de Bézout

Probaremos que en cada paso, el MCD se conserva:

$\gcd(a, b) = \gcd(b, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{k-1}, r_k) = \gcd(r_k, 0) = r_k.$

Lema. Si $a = bq + r$, entonces $\gcd(a, b) = \gcd(b, r)$.

Demostración del lema. Sea $d = \gcd(a, b)$. Por la linealidad de la divisibilidad: $d \mid a$ y $d \mid b$ implica $d \mid (a - bq) = r$, luego $d$ es divisor común de $b$ y $r$. Recíprocamente, cualquier divisor común de $b$ y $r$ divide $bq + r = a$, así que también es divisor común de $a$ y $b$. Por tanto el conjunto de divisores comunes de $(a, b)$ y de $(b, r)$ es el mismo, y sus máximos coinciden. $\blacksquare$

Terminación. La sucesión $b > r_1 > r_2 > \cdots \geq 0$ es estrictamente decreciente (cada resto es positivo por hipótesis hasta el último) y acotada inferiormente por $0$. Por el principio del buen orden, termina. $\blacksquare$

Complejidad. Se puede demostrar (lema de Gabriel Lamé, 1844) que el número de pasos es a lo sumo $5$ veces el número de dígitos decimales de $\min(a, b)$, es decir $O(\log \min(a, b))$ divisiones.

Sea $S = \{ax + by : x, y \in \mathbb Z\} \cap \mathbb Z_{>0}$ el conjunto de combinaciones lineales positivas. Como $|a|, |b| \in S$ (tomando $x = \text{sign}(a), y = 0$ o similar), $S$ es no vacío. Por el buen orden, $S$ tiene un mínimo, digamos $d = ax_0 + by_0$.

Afirmamos $d = \gcd(a, b)$.

$d \mid a$: por la división euclidiana, $a = dq + r$ con $0 \leq r < d$. Entonces $r = a - dq = a(1 - qx_0) + b(-qy_0) \in \{ax+by\} \cap \mathbb Z_{\geq 0}$. Si $r > 0$, entonces $r \in S$ y $r < d$, contradiciendo la minimalidad de $d$. Luego $r = 0$ y $d \mid a$.

$d \mid b$: análogo.

Es el máximo divisor común: cualquier divisor común de $a$ y $b$ divide $ax_0 + by_0 = d$. Por la propiedad de acotación, ese divisor es $\leq d$. Luego $d$ es efectivamente el máximo. $\blacksquare$

Supongamos $\gcd(a, n) = 1$ (tomamos $n = p$ para el caso del primo). Por Bézout, existen $u, v$ con $au + nv = 1$. Multiplicando por $b$:

$aub + nvb = b.$

Como $n \mid ab$, se tiene $n \mid aub$. Y trivialmente $n \mid nvb$. Por linealidad, $n \mid aub + nvb = b$. $\blacksquare$

Este lema es la clave para la unicidad en el Teorema Fundamental de la Aritmética.

Necesidad. Si $ax + by = c$, como $d \mid a$ y $d \mid b$, entonces $d \mid c$.

Suficiencia. Si $d \mid c$, sea $c = dk$. Por Bézout, $d = au + bv$ para algunos $u, v$. Entonces $(x_0, y_0) = (uk, vk)$ es una solución particular: $a(uk) + b(vk) = k(au + bv) = kd = c$.

Familia de soluciones. Si $(x, y)$ y $(x_0, y_0)$ son soluciones, restando:

$a(x - x_0) + b(y - y_0) = 0 \implies \frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0).$

Como $\gcd(a/d, b/d) = 1$, el Lema de Euclides aplicado a $\frac{a}{d} \mid \frac{b}{d}(y_0 - y)$ da $\frac{a}{d} \mid (y_0 - y)$. Análogamente $\frac{b}{d} \mid (x - x_0)$. Escribiendo $x - x_0 = \frac{b}{d} t$, se obtiene $y - y_0 = -\frac{a}{d} t$. $\blacksquare$