\( \newcommand{\Implies}{\Rightarrow} \newcommand{\Iff}{\Leftrightarrow} \renewcommand{\emptyset}{\varnothing} \newcommand{\powersetsym}{\mathcal{P}} \newcommand{\fto}{\rightarrow} \newcommand{\mto}{\mapsto} \newcommand{\Cx}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Ns}{\mathbb{N}^*} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\K}{\mathbb{K}} \newcommand{\vv}[1]{\boldsymbol{#1}} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{ \left\|#1\right\| } \newcommand{\pnorm}[1]{\left\|#1\right\|_p} \newcommand{\supnorm}[1]{\left\|#1\right\|_\infty} \newcommand{\innerprod}[1]{\left\langle #1\right\rangle} \newcommand{\Ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\Floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\Conj}[1]{\overline{#1}} \newcommand{\arccot}{\mathop{\text{arc\,cot}}\nolimits} \newcommand{\arcsec}{\mathop{\text{arc\,sec}}\nolimits} \newcommand{\arccsc}{\mathop{\text{arc\,csc}}\nolimits} \renewcommand{\arg}{\mathop{\text{arg}}\nolimits} \newcommand{\mcd}[1]{\mathop{\text{mcd}}\left(#1\right)} \newcommand{\mcm}[1]{\mathop{\text{mcm}}\left(#1\right)} \renewcommand{\ker}{\mathop{\text{ker}}\nolimits} \newcommand{\grad}{\mathop{\text{grad}}\nolimits} \newcommand{\dom}{\mathop{\text{dom}}\nolimits} \newcommand{\rng}{\mathop{\text{ran}}\nolimits} \newcommand{\diam}{\mathop{\text{diam}}\nolimits} \newcommand{\Obj}{\mathop{\text{obj}}\nolimits} \newcommand{\Hom}{\mathop{\text{hom}}\nolimits} \newcommand{\End}{\mathop{\text{end}}\nolimits} \newcommand{\Aut}[1]{\mathop{\mathrm{aut}}\nolimits(#1)} \newcommand{\Inn}[1]{\mathop{\mathrm{int}}\nolimits(#1)} \newcommand{\Deg}{\mathop{\mathrm{grad}}\nolimits} \newcommand{\Img}{\mathop{\text{im}}\nolimits} \newcommand{\Id}{\mathop{\mathrm{id}}\nolimits} \newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits} \renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits} \renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits} \newcommand{\Char}{\mathop{\mathrm{car}}\nolimits} \renewcommand{\mod}[1]{\mathop{(\mathop{\text{mód}}\nolimits #1)}} \newcommand{\res}{\mathop{\text{mód}}} \newcommand{\categof}[1]{\mathsf{#1}} \newcommand{\CC}{\categof{C}} \newcommand{\CONJ}{\categof{Conj}} \newcommand{\SET}{\categof{Set}} \newcommand{\GRP}{\categof{Grp}} \newcommand{\AGRP}{\categof{Ab}} \newcommand{\morph}[1]{\mathrel{\mathop{\longrightarrow}\limits^{#1}}} \newcommand{\subgr}{\leq} \newcommand{\nsubgr}{\mathrel{\unlhd}} \newcommand{\iso}{\cong} \newcommand{\genby}[1]{\left\langle #1\right\rangle} \newcommand{\symgr}[1][n]{S_{#1}} \newcommand{\GenOf}[1]{\mathop{\text{gen}}\left(#1\right)} \newcommand{\normalizer}[2][G]{{\mathbf N}_{#1}(#2)} \newcommand{\centralizer}[2][G]{{\mathbf C}_{#1}(#2)} \newcommand{\orbit}[2][G]{\mathcal{O}_{#1}(#2)} \newcommand{\stab}[2][G]{#1(#2)} \newcommand{\GL}[2][n]{\mathrm{GL}(#1,#2)} \newcommand{\SL}[2][n]{\mathrm{SL}(#1,#2)} \newcommand{\Ort}[2][n]{\mathrm{O}(#1,#2)} \newcommand{\SO}[2][n]{\mathrm{SO}(#1,#2)} \newcommand{\KleinV}{\mathbf{V}}\)

1.2 La identidad de Bézout

El teorema siguiente establece una caracterización importante del máximo común divisor.

Teorema 1.13 (Identidad de Bézout). Para cualesquiera enteros no nulos \(x\) y \(y\) existen enteros \(s\) y \(t\) tales que \(sx + ty = \mcd {x,y}\). Con más detalle, \(\mcd {x,y}\) es el menor de los enteros positivos de la forma \(sx + ty\) con \(s,t\in \Z \).
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, digamos \( 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\).
Definición 1.14. Si \(x_1,\ldots ,x_n\), son enteros, a los enteros de la forma \[ s_1 x_1 + \cdots + s_n x_n, \] con \(s_1,\ldots ,s_n\in \Z \), los llamamos combinaciones lineales de \(x_1,\ldots ,x_n\).
Proposición 1.15. Si \(x\in \Z \) divide a cada uno de los enteros \(y_1,\ldots ,y_n\), entonces \(x\) divide a toda combinación lineal de éstos.

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.

Corolario 1.16. Si \(x\) y \(y\) son enteros no nulos, la ecuación \(sx + ty = n\) tiene soluciones enteras \(s\) y \(t\) si y sólo si \(n\) es un múltiplo de \(\mcd {x,y}\). En particular, \(sx + ty = n\) siempre tiene soluciones cuando \(x\) y \(y\) son primos relativos.
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: \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 teorema 1.16. Resolviendo para cada residuo en las ecuaciones de arriba y sustituyendo de abajo hacia arriba, obtenemos \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 \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 \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.

Ejercicio 1.19. Encontrar enteros \(x\neq 405\) y \(y\neq -162\) tales que \(91x + 221y = 1053\).
Solución: Ya que contamos con las soluciones \(x=405\) y \(y=-162\), podemos investigar valores enteros \(a\) y \(b\) tales que \[ 91(405 + a) + 221(-162 + b) = 1053. \] Despejando \(a\), observamos que dichos números deben satisfacer \(b = -7a / 17\), luego basta elegir \(a\) como cualquier múltiplo de \(17\). Por ejemplo, para \(a = 17\) tenemos \(b = -7\), y en efecto \[ 91(405 + 17) + 221(-162 - 7) = 91(422) + 221(-169) = 1053, \] así que \(x = 422\) y \(y = -169\) constituyen otro par de soluciones enteras a la ecuación \(91x + 221y = 1053\).

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:

Corolario 1.20. Dos enteros \( x \) y \( y \) son primos relativos si y sólo si existen enteros \( s \) y \( t \) tales que \( sx + ty = 1 \).
Corolario 1.21. Para cualesquiera \( x,y\in \Z \), \( d = \mcd {x,y} \) si y sólo si \( x/d \) y \( y/d \) son primos relativos.
Corolario 1.22. Sean \( a,x,y\in \Z \). Si \( a\mid xy \) y \( \mcd {a,x} = 1 \), entonces \( a\mid y \).
Demostración: Puesto que \( \mcd {a,x} = 1 \), el teorema 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 \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 \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 teorema 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 \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 teorema 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).