\(
\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).