Álgebra abstracta
1.2 Identidad de Bézout
El teorema siguiente establece una caracterización importante del máximo común divisor.
-
Demostración: Sea \(S = \{kx + ly \mid k,l\in \Z , kx + ly > 0\}\). Este conjunto es no vacío, pues, por ejemplo, \(xx + yy = x^2 + y^2 > 0\). Por lo tanto, el principio de buen ordenamiento de \(\N \) nos dice que \(S \) tienen un mínimo, sigamos \(d = sx + ty \). Vamos a comprobar que \(d = \mcd {x,y} \). Por el algoritmo de la división, \(x = qd + r \) con \(0\leq r < d \). Puesto que
\[ r = x - qd = x - q(sx + ty) = x - qsx - qty = (1-qs)x + (-qt)y, \]
no puede ser \(r > 0\), pues de otro modo \(r\) estaría en \(S\), en contradicción con la minimalidad de \(d\) en \(S\). Por lo tanto, debemos tener \(r = 0\), así que \(d\mid x\). De manera similar se comprueba que \(d\mid y\), por lo que \(d\) es un divisor común de \(x\) y \(y\). Si \(d'\) es otro divisor común de \(x\) y \(y\), existen \(a,b\in \Z \) tales que \(d = sx + ty = sad' + tbd'\), lo que muestra que \(d'\mid d\) y por tanto \(d\) tiene que ser el máximo común divisor de \(x\) y \(y\).
La proposición anterior, cuya demostración es inmediata y se deja como ejercicio al lector, nos dice en particular que toda combinación lineal de \(x\) y \(y\) es un múltiplo de su máximo común divisor. Recíprocamente, se deduce de la identidad de Bézout que todo múltiplo de \(\mcd {x,y}\) es una combinación lineal de \(x\) y \(y\), pues \(d \) es él mismo una combinación lineal de \(x \) y \(y \). Así pues, las únicas combinaciones lineales de \(x \) y \(y \) son los múltiplos de \(\mcd {x,y} \). Tenemos así la siguiente consecuencia de la la identidad de Bézout.
-
Ejemplo 1.17. Encontraremos las soluciones enteras a la ecuación \(280s + 231t = 21\). Lo primero es encontrar el máximo común divisor de \(x \) y \(y \) mediante el algoritmo de Euclides, que resulta en los pasos siguientes:
\(\seteqnumber{0}{1.}{1}\)\begin{align*} 280 & = 1(231)+49, \\ 231 & = 4(49)+35, \\ 49 & = 1(35)+14, \\ 35 & = 2(14)+7, \\ 14 & = 2(7). \end{align*} Tenemos pues que \(\mcd {280,231} = 7\). Puesto que 7 divide a 21, la ecuación planteada sí tiene soluciones enteras según lo afirma el corolario 1.16. Resolviendo para cada residuo en las ecuaciones de arriba y sustituyendo de abajo hacia arriba, obtenemos
\(\seteqnumber{0}{1.}{1}\)\begin{align*} 7 & = 35 - 2(14) \\ & = [231 - 4(49)] - 2[49 - (231 - 4(49))] \\ & = 3(231) - 14(49) \\ & = 3(231) - 14(280 - 231) \\ & = -14(280) + 17(231). \end{align*} Por lo tanto, \(21 = -42(280) + 51(231)\), así que las soluciones a la ecuación del problema son \(s=-42\), \(t=51\).
-
Ejemplo 1.18. Encontraremos enteros \(x\) y \(y\) tales que \(91x + 221y = 1053\). Mediante el algoritmo de Euclides, obtenemos
\(\seteqnumber{0}{1.}{1}\)\begin{align*} 221 & = 2(91) + 39, \\ 91 & = 2(39) + 13, \\ 39 & = 3(13), \end{align*} por lo que \(\mcd {91,221} = 13\), el cual divide a \(1053\) y así sabemos que la ecuación \(91x + 221y = 1053\) sí tiene soluciones enteras. Trabajando con este desarrollo del algoritmo de Euclides de abajo hacia arriba, encontramos que
\(\seteqnumber{0}{1.}{1}\)\begin{align*} 13 & = 91 - 2(39) \\ & = 91 - 2(221 - 2(91)) \\ & = 5(91) - 2(221). \end{align*} Multiplicando ambos miembros por 81, obtenemos
\[ 91(405) - 221(162) = 1053, \]
así que las soluciones de la ecuación son \(x=405\) y \(y=-162\).
Las soluciones encontradas con el procedimiento de los ejemplos anteriores no son únicas. El ejercicio siguiente solicita al lector encontrar soluciones distintas para el ejemplo anterior.
Recordemos que dos enteros \(x \) y \(y \) se dicen primos relativos cuando no tienen más divisor común que la unidad, o sea que \(\mcd {x,y} = 1 \). La identidad de Bézout nos da una forma alternativa de caracterizar esta situación:
-
Demostración: Puesto que \(\mcd {a,x} = 1 \), el corolario 1.20 nos dice que existen \(s,t\in \Z \) tales que \(sa + tx = 1 \), o sea que \(y = say + txy \), donde cada término es divisible entre \(a \), luego \(a\mid y \).
-
Teorema 1.23. Sean \(a \), \(b \) y \(c \) enteros, donde \(a \) y \(b \) no son ambos nulos. Entonces la ecuación
\(\seteqnumber{0}{1.}{1}\)\begin{equation} \label {eq:ecu rel Bezout solu} ax + by = c \end{equation}
tiene soluciones enteras \(x \) y \(y \) si y sólo si \(c \) es un múltiplo de \(d = \mcd {a,b}\). De hecho, en ese caso la ecuación tiene infinitas soluciones, todas ellas de la forma
\(\seteqnumber{0}{1.}{2}\)\begin{equation} \label {ec:forma solu rel Bezout} x = x_0 + \frac {bn}{d},\qquad y=y_0-\frac {an}{d}, \end{equation}
donde \(x_0 \) y \(y_0 \) son cualquier solución particular y donde \(n \) es un entero cualquiera.
-
Demostración: La existencia de las soluciones, tal y como lo afirma el teorema, es simplemente lo que dice el corolario 1.16. Ahora bien, si \(x_0 \) y \(y_0 \) constituyen una solución particular de la ecuación (1.2), \(d = \mcd {x,y} \) y \(n \) es cualquier entero, entonces
\[ a\left ( x_0 + \frac {bn}{d} \right ) + b\left ( y_0 - \frac {an}{d} \right ) = ax_0 + by_0 = c, \]
o sea que \(x = x_0 + \frac {bn}{d} \) y \(y = y_0 - \frac {an}{d} \) también es una solución. Puesto que \(n \) es un entero arbitrario, estas fórmulas nos dan infinitas soluciones de la ecuación (1.2). Para demostrar que de hecho las únicas soluciones son aquellas dadas por tales fórmulas, supongamos que \(x,y \) son enteros que cumplen \(ax + by = ax_0 + by_0 = c \). Entonces
\[ a(x - x_0) + b(y - y_0) = 0, \]
de donde se sigue que
\(\seteqnumber{0}{1.}{3}\)\begin{equation} \label {ec:ecu rel Bezout solu demo} \frac {a}{d}(x - x_0) = -\frac {b}{d}(y - y_0) \end{equation}
Por hipótesis, al menos uno de los enteros \(a \) y \(b \) es no nulo, digamos \(b \neq 0 \) (si \(a \) fuese el entero no nulo, el razonamiento que sigue es prácticamente idéntico). Entonces \(\frac {b}{d} \) divide al lado izquierdo de la ecuación de arriba, y como no divide a \(\frac {a}{d} \) (pues \(b/d \) y \(a/d \) son primos relativos de acuerdo con el corolario 1.21), \(b / d \) tiene que dividir a \(x - x_0 \), luego existe un entero \(n \) tal que
\[ \frac {bn}{d} = (x - x_0), \]
o sea que \(x = x_0 + \frac {bn}{d} \). Sustituyendo en (1.4) y despejando \(y \), encontramos que \(y = y_0 - \frac {an}{d} \). Queda así demostrado que, cuando la ecuación (1.2) tiene soluciones, éstas son infinitas y todas ellas están dadas por las fórmulas dadas en (1.3).