1.10: Coeficientes de cómputos para el lema de Bezout
- Page ID
- 117423
Aunque la prueba del Lema de Bezout en el último capítulo simplemente mostró que, dados enteros\(a\) y coeficientes\(s\) y\(b\)\(t\) existen de tal manera que\(\gcd(a,b)=sa+tb\), modificaciones adecuadas del Algoritmo Euclideano nos dan formas de computar estos coeficientes. En este capítulo discutimos dos de esas formas, conocidas como el Algoritmo Euclideano Extendido y el Método de Blankinship.
El Algoritmo Euclidiana Extendido
Con el Algoritmo Euclideano Extendido, la idea es reorganizar y sustituir en las ecuaciones que surgen del Algoritmo de División durante el Algoritmo Euclideano, para llegar a una expresión de\(\gcd(a,b)\) como una combinación lineal de\(a\) y\(b\).
Supongamos que el Algoritmo Euclidiana produce las siguientes ecuaciones:\[\begin{aligned} a &=bq_0+r_0;\\ b &=r_0q_1+r_1;\\ r_0 &=r_1q_2+r_2;\\ &\qquad\vdots\\ r_{k-2} &=r_{k-1}q_k+r_k;\\ r_{k-1} &=r_kq_{k+1}.\end{aligned}\]
Suponiendo que ese\(r_k\) es el último resto distinto de cero, eso lo sabemos\(\gcd(a,b)=r_k\). Supongamos que omitimos la última ecuación anterior y resolvemos el resto de estas ecuaciones para el término restante. Si luego los ordenamos de último a primero, obtenemos una nueva secuencia de ecuaciones (mostramos algunas más de las últimas ecuaciones en la lista):
\[\begin{aligned} r_k &= r_{k-1}q_k-r_{k-2};\\ r_{k-1} &= r_{k-2}q_{k-1}-r_{k-3};\\ r_{k-2} &= r_{k-3}q_{k-2}-r_{k-4};\\ &\qquad\vdots\\ r_2 &= r_1q_2-r_0;\\ r_1 &= r_0q_1-b;\\ r_0 &= bq_0-a;\\\end{aligned}\]
Ahora mira la primera de estas nuevas ecuaciones. Dado que el Algoritmo Euclides produce\(\gcd(a,b)\), en realidad podemos escribir\[\label{eqgcd}\gcd(a,b) = r_{k-1}q_k - r_{k-2}.\] Aquí vemos que\(\gcd(a,b)\) es una combinación lineal de\(r_{k-1}\) y\(r_{k-2}\). Como preferiríamos tener\(\gcd(a,b)\) como una combinación lineal de algo más (es decir,\(a\) y\(b\)), sería bueno reemplazarlo\(r_{k-1}\) y\(r_{k-2}\) por expresiones que involucran\(a\) y \(b\). Dará algunos pasos, pero esto es exactamente lo que vamos a hacer.
Observe que la segunda ecuación,\(r_{k-1} = r_{k-2}q_{k-1}-r_{k-3}\), nos dice lo que\(r_{k-1}\) es igual. Usemos esto en la ecuación\(\eqref{eqgcd}\), sustituyendo por\(r_{k-1}\); esto rinde\[\label{eqgcd2} \gcd(a,b) = (r_{k-2}q_{k-1}-r_{k-3})q_k-r_{k-2},\] lo que podemos reorganizar como\[\gcd(a,b) = (q_{k-1}q_k - 1)r_{k-2}-q_k r_{k-3}.\nonumber \]
En este punto\(\gcd(a,b)\) es una combinación lineal de\(r_{k-2}\) y\(r_{k-3}\) (en lugar de una combinación de\(r_{k-1}\) y\(r_{k-2}\), como era anteriormente). Si hacemos otra sustitución usando la ecuación\(r_{k-2} = r_{k-3}q_{k-2}-r_{k-4}\), obtendremos\[\begin{aligned} \gcd(a,b) &= (q_{k-1}q_k - 1)(r_{k-3}q_{k-2}-r_{k-4})-q_k r_{k-3}\\ &= (q_{k-2}q_{k-1}q_k - q_{k-2}-q_k )r_{k-3}-(q_{k-1}q_k - 1)r_{k-4},\end{aligned}\] en cuál\(\gcd(a,b)\) es ahora en términos de\(r_{k-3}\) y\(r_{k-4}\).
En este punto las ecuaciones se están desordenando, así que no continuaremos con las sustituciones (en cambio, trabajaremos un ejemplo a continuación). La idea, sin embargo, es simple; al trabajar nuestro camino hacia atrás a través de las ecuaciones producidas por el Algoritmo Euclidiana, podemos expresarnos\(\gcd(a,b)\) como combinaciones lineales que se acercan progresivamente a la combinación lineal de\(a\) y\(b\) que necesitamos.
Para nuestro ejemplo, continuaremos con los números utilizados en el Ejemplo 1.8.1 de la Sección 1.8. Ahí encontramos eso\(\gcd(803,154) = 11\). Lemma de Bezout lo garantiza\(11 = 803s+154t\) para algunos enteros\(s,t\). Determinemos una posible elección de\(s\) y\(t\).
En el Ejemplo 1.8.1 encontramos lo siguiente:\[\begin{aligned} 803 &=154\cdot5+33 \\ 154 &=33\cdot4+22 \\ 33 &=22\cdot1+11 \\ 22 &=11\cdot2+0.\end{aligned}\]
Reordenando y reordenando todas menos la última de estas ecuaciones, obtenemos
\[\begin{aligned} 11 &=33-22\cdot1\\ 22 &=154-33\cdot4 \\ 33 &= 803-154\cdot5\end{aligned}\]
Ahora nos pusimos a punto de encontrar una expresión de\(11\) como una combinación lineal de\(803\) y\(154\). Comenzando con la ecuación\(11 = 33 - 22\cdot 1\), sustituimos\(22=154-33\cdot 4\) (la siguiente ecuación) para obtener\[\begin{aligned} 11 &= 33 - (154-33\cdot 4)\cdot 1\\ &= 5 \cdot 33 - 1 \cdot 154.\end{aligned}\]
Ahora vamos a sustituir por 33, usando la ecuación\(33 = 803-154 \cdot 5\) anterior:\[1 = 5 \cdot (803-154 \cdot 5) - 1 \cdot 154\nonumber \] y finalmente obtendremos\[\boxed{11 = 5 \cdot 803 - 26 \cdot 154.}\nonumber \]
Hemos llegado a una expresión para\(\gcd(803,154)\) como una combinación lineal de\(803\) y\(154\), como lo describe el Lema de Bezout, con\(s=5\) y\(t=-26\) en la combinación lineal.
Método de Blankinship
Una característica del Algoritmo Euclidiana Extendido que se acaba de discutir es que para encontrar los coeficientes\(s\) y\(t\) en el Lema de Bezout, debemos realizar un seguimiento de los cocientes y restos utilizados en la realización del Algoritmo Euclideano (original), para que podamos encontrar \(s\)y\(t\) “trabajando hacia atrás” a través de esta información una vez que el Algoritmo Euclideano básico haya terminado.
En esta sección vemos un enfoque sencillo para encontrar\(s\) y\(t\) que apareció en un artículo de W.A Blankinship en la edición agosto-septiembre de 1963 del American Mathematical Monthly. \(^{1}\)A diferencia del Algoritmo Euclideano Extendido, el método de Blankinship produce los enteros\(s\) y\(t\) en el Lema de Bezout al mismo tiempo produce\(\gcd(a,b)\).
Dado\(a>b>0\) empezamos con la matriz\[\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1 \end{bmatrix}\nonumber \] Luego seguimos agregando múltiplos de una fila a otra fila, alternando elección de filas hasta llegar a una matriz de la forma\[\begin{bmatrix} 0 & x_1 & x_2 \\ d & y_1 & y_2 \end{bmatrix}\nonumber \] o\[\begin{bmatrix} d & y_1 & y_2 \\ 0 & x_1 & x_2 \end{bmatrix}\nonumber \] en otras palabras, el objetivo es obtener una\(0\) en la primera columna. Una vez que lleguemos a una de estas formas, será cierto que\(d=\gcd(a,b)=y_1a+y_2b\).
Primera toma\(a=35\),\(b=15\). \[\begin{bmatrix} 35 & 1 & 0 \\ 15 & 0 & 1 \end{bmatrix}\nonumber \]Nota\(35=15\cdot 2+5\), de ahí\[35+15(-2)=5.\nonumber \] Así multiplicamos fila\(2\) por\(-2\) y la agregamos a fila\(1\), obteniendo\[\begin{bmatrix} 5 & 1 & -2 \\ 15 & 0 & 1 \end{bmatrix}\nonumber \] Ahora\(3\cdot 5=15\) o\(15+(-3)5=0\), así multiplicamos fila\(1\) por \(-3\)y agregarlo a fila\(2\), consiguiendo\[\begin{bmatrix} 5 & 1 & -2 \\ 0 & -3 & 7 \end{bmatrix}.\nonumber \] Ahora podemos decir eso\[\boxed{\gcd(35,15)=5}\nonumber \] y\[\boxed{5=1\cdot 35+(-2)\cdot 15.}\nonumber \]
Consideremos ahora un ejemplo más complicado: Tomemos\(a=1876\),\(b=365\). \[\begin{bmatrix} 1876 & 1 & 0 \\ 365 & 0 & 1 \end{bmatrix}\nonumber \]Ahora\(1876=365\cdot5+51\) así agregamos\(-5\) veces la segunda fila a la primera fila, obteniendo:\[\begin{bmatrix} 51 & 1 & -5 \\ 365 & 0 & 1 \end{bmatrix}\nonumber \] Ahora\(365=51\cdot7+8\), así agregamos\(-7\) tiempos fila\(1\) a fila\(2\), obteniendo:\[\begin{bmatrix} 51 & 1 & -5 \\ 8 & -7 & 36 \end{bmatrix}\nonumber \] Ahora \(51=8\cdot 6+3\), entonces agregamos\(-6\) tiempos fila\(2\) a fila\(1\), obteniendo:\[\begin{bmatrix} 3 & 43 & -221 \\ 8 & -7 & 36 \end{bmatrix}\nonumber \] Ahora\(8=3\cdot 2+2\), entonces agregamos\(-2\) tiempos fila\(1\) a fila\(2\), obteniendo:\[\begin{bmatrix} 3 & 43 & -221 \\ 2 & -93 & 478 \end{bmatrix}\nonumber \] Entonces \(3=2\cdot 1+1\), entonces agregamos\(-1\) tiempos fila\(2\) a fila\(1\), obteniendo:\[\begin{bmatrix} 1 & 136 & -699 \\ 2 & -93 & 478 \end{bmatrix}\nonumber \] Finalmente,\(2=1\cdot 2\) así que si agregamos\(-2\) tiempos fila\(1\) a fila\(2\) obtenemos: \[\label{eq: Blankenship matrix} \begin{bmatrix} 1 & 136 & -699 \\ 0 & -365 & 1876 \end{bmatrix}.\]Esto nos dice que\[\boxed{\gcd(1876,365)=1}\nonumber \] y\[\label{eq: Blankenship matrix 2} \boxed{1=136\cdot 1876+(-699)365.}\] Tenga en cuenta que no fue necesario computar las dos últimas entradas\(-365\) y\(1876\) en ecuación\(\eqref{eq: Blankenship matrix}\). Sin embargo, es una buena idea comprobar que la ecuación se\(\eqref{eq: Blankenship matrix 2}\) mantiene. En este caso tenemos:\[\begin{array}{rrr}136\cdot 1876&=&255136 \\ \underline{(-699)\cdot 365}&=&\underline{-255135 } \\ &&1\end{array}\nonumber\] Entonces es correcto.
Por qué funciona el Método de Blankinship: Mirando justamente lo que sucede en la primera columna, tenga en cuenta que estamos llevando a cabo el Algoritmo Euclidiana, así que cuando un elemento en columna\(1\) es\(0\), el otro es, de hecho, el\(\gcd\). Tenga en cuenta que al inicio tenemos\[\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1 \end{bmatrix}\nonumber \] y\[\begin{aligned} a &=1\cdot a+0\cdot b \\ b &=0\cdot a+1\cdot b.\end{aligned}\] Uno puede demostrar que en cada paso intermedio siempre\[\begin{bmatrix} a_1 & x_1 & x_2 \\ b_1 & y_1 & y_2 \end{bmatrix}\nonumber \] tenemos\[\begin{aligned} a_1 &=x_1a+x_2b \\ b_1 &=y_1a+y_2b,\end{aligned}\] y el resultado sigue. Omitiremos los detalles.
Ejercicios
Utilice el Algoritmo Euclidiana Extendido para calcular el\(s\) y\(t\) en el Lema de Bezout para cada uno de los siguientes valores de\(a\) y\(b\).
- \(a=267\),\(b=112\)
- \(a=216\),\(b=135\)
- \(a=11312\),\(b=11321\)
Utilice el Método de Blankinship para calcular el\(s\) y\(t\) en el Lema de Bezout para cada uno de los pares\(a,b\) de enteros en el ejercicio anterior.
Demuéstralo si\(1=as+bt\) entonces\(\gcd(a,b)=1\).
Demostrar que siempre\(s,t\) son números enteros haciendo\(as+bt = \gcd(a,b)\), entonces\(\gcd(s,t)=1\).
- Encuentra números enteros\(a\),\(b\),\(d\),\(s\), de\(t\) tal manera que todos los siguientes tienen
- \(a>0\),\(b>0\),
- \(d=sa+tb\), y
- \(d\ne\gcd(a,b)\).
- Explique por\(d\) qué el que eligió en la parte (a) no puede ser\(1\).
- ¿Qué te muestra tu ejemplo (es decir, los enteros\(a,b,d,s,t\)) en la parte (a) sobre las combinaciones lineales de\(a\) y\(b\)?
Notas al pie
[1] Gracias a Chris Miller por traer este método a mi atención|W.E. Clark.