Lección 1.2: La identidad de Bézout — Espinoza Olimpiadas

¿Qué es la identidad de Bézout?

En la lección anterior vimos que el MCD de dos números puede calcularse con el algoritmo de Euclides. Pero ese algoritmo guarda un secreto más poderoso: no solo nos dice cuánto vale $\gcd(a,b)$ , sino que nos da receta explícita para escribirlo como combinación lineal entera de $a$ y $b$ .

Teorema de Bézout: para todo par de enteros $a, b$ (no ambos cero), existen enteros $x, y$ tales que $ax + by = \gcd(a,b)$ . A la ecuación $ax + by = d$ con $d = \gcd(a,b)$ se la llama la identidad de Bézout del par $(a, b)$ .

Este resultado es la llave de entrada a ecuaciones diofánticas, inversos modulares y una decena de argumentos olímpicos clásicos. No es un adorno teórico: es la herramienta.

ax + by = \gcd(a,b) \quad \text{tiene solución entera } (x, y)

El algoritmo extendido de Euclides paso a paso

El algoritmo extendido corre el algoritmo de Euclides hacia delante anotando los cocientes, y luego substituye hacia atrás. Veamos un ejemplo completo: encontrar $x, y$ con $252x + 105y = \gcd(252, 105)$ .

Paso 1 — Euclides hacia adelante. Dividimos sucesivamente: $252 = 2 \cdot 105 + 42$ , luego $105 = 2 \cdot 42 + 21$ , luego $42 = 2 \cdot 21 + 0$ . El MCD es $21$ .

Paso 2 — Substitución hacia atrás. De la segunda ecuación: $21 = 105 - 2 \cdot 42$ . Reemplazamos $42 = 252 - 2 \cdot 105$ : $21 = 105 - 2(252 - 2 \cdot 105) = 105 - 2 \cdot 252 + 4 \cdot 105 = 5 \cdot 105 - 2 \cdot 252$ . Identidad de Bézout: $252 \cdot (-2) + 105 \cdot 5 = 21$ .

252\cdot(-2) + 105\cdot 5 = 21 = \gcd(252,105)

El método tabular: sin confundirse en los signos

En competencias conviene una organización en tabla. Mantenemos dos filas $(s_i, t_i)$ tales que $s_i \cdot a + t_i \cdot b$ es igual al $i$ -ésimo resto de Euclides. Empezamos con $(s_0, t_0) = (1, 0)$ y $(s_1, t_1) = (0, 1)$ , y actualizamos: si el cociente en el paso $i$ es $q_i$ , entonces $(s_{i+1}, t_{i+1}) = (s_{i-1} - q_i s_i,\; t_{i-1} - q_i t_i)$ .

Para $a = 252$ , $b = 105$ : fila 0 es $(1, 0)$ con resto $252$ ; fila 1 es $(0, 1)$ con resto $105$ ; cociente $q=2$ , fila 2: $(1-2\cdot0, 0-2\cdot1)=(1,-2)$ con resto $42$ ; cociente $q=2$ , fila 3: $(0-2\cdot1, 1-2\cdot(-2))=(-2,5)$ con resto $21$ . Leemos $(-2, 5)$ : efectivamente $252(-2)+105(5)=21$ .

Este método es infalible en exámenes porque los signos se rastrean automáticamente. Si tienes cuatro pasos de Euclides, la tabla tiene cuatro filas y el resultado salta directo. En olympiadas con restricción de tiempo, dominar esta mecánica puede marcar la diferencia.

El Lema de Euclides: la consecuencia más importante

Lema de Euclides: si $\gcd(a, n) = 1$ y $n \mid ab$ , entonces $n \mid b$ . En palabras: si $n$ es coprimo con $a$ pero divide al producto $ab$ , entonces forzosamente divide a $b$ .

Demostración con Bézout: como $\gcd(a, n) = 1$ , existen $x, y$ enteros con $ax + ny = 1$ . Multiplicamos ambos lados por $b$ : $abx + nby = b$ . Ahora $n \mid ab$ por hipótesis, así que $n \mid abx$ , y claramente $n \mid nby$ . Por tanto $n \mid b$ . La demostración es de tres líneas.

Aplicación directa: si $p$ es primo y $p \mid ab$ , entonces $p \mid a$ o $p \mid b$ . Esto se sigue del lema porque si $p \nmid a$ entonces $\gcd(p, a) = 1$ (los únicos divisores de $p$ son $1$ y $p$ ), así que $p \mid b$ . Este hecho es la base del Teorema Fundamental de la Aritmética, que veremos en el capítulo 2.

\gcd(a,n)=1 \text{ y } n\mid ab \implies n\mid b

Ecuaciones diofánticas lineales: cuándo tienen solución

Una ecuación diofántica lineal tiene la forma $ax + by = c$ donde $a, b, c$ son enteros dados y buscamos soluciones enteras $(x, y)$ . ¿Cuándo existe solución? **Exactamente cuando $\gcd(a,b) \mid c$ .** La demostración es directa: cualquier valor $ax + by$ es múltiplo de $\gcd(a,b)$ , así que si $\gcd(a,b) \nmid c$ no hay solución; si $\gcd(a,b) \mid c$ , tomamos la identidad de Bézout $ax_0 + by_0 = \gcd(a,b)$ y multiplicamos por $c/\gcd(a,b)$ .

Encontrando todas las soluciones: si $(x_0, y_0)$ es una solución particular de $ax + by = c$ , entonces todas las soluciones enteras son $x = x_0 + \frac{b}{d}t$ , $y = y_0 - \frac{a}{d}t$ , con $d = \gcd(a,b)$ y $t \in \mathbb{Z}$ . Esto parametriza la recta entera de soluciones.

Ejemplo ONEM: ¿Tiene la ecuación $15x + 21y = 9$ solución entera? Calculamos $\gcd(15,21)=3$ y como $3 \mid 9$ , sí tiene. Una solución de $15x+21y=3$ : corriendo Euclides, $3 = 3\cdot15 - 2\cdot21$ , así $x_0 = 3$ , $y_0 = -2$ . Multiplicando por $3$ : $(x_0, y_0)=(9, -6)$ es una solución particular. La familia completa: $x = 9 + 7t$ , $y = -6 - 5t$ para $t \in \mathbb{Z}$ .

ax+by=c \text{ tiene solución entera} \iff \gcd(a,b)\mid c

Resumen y panorama

El algoritmo extendido de Euclides es la segunda capa de la teoría de divisibilidad. El algoritmo básico da el MCD; el extendido da los coeficientes de Bézout; de los coeficientes salen el Lema de Euclides y la clasificación de ecuaciones diofánticas lineales.

En olimpiadas, los tres usos más frecuentes de Bézout son: (1) demostrar que $\gcd(a,b)=1$ construyendo una combinación lineal igual a $1$ ; (2) resolver $ax \equiv c \pmod{n}$ cuando $\gcd(a,n)=1$ , encontrando el inverso modular de $a$ ; (3) argumentar con el Lema de Euclides para extraer factores de productos.

La lección 1.3 cambia de tema pero mantiene el espíritu: criterios de divisibilidad, que son otra forma de detectar divisores sin hacer divisiones largas. Después, en el capítulo 6, regresaremos a las ecuaciones diofánticas con técnicas más sofisticadas.

La identidad de Bézout