1.9: Lema de Bezout
- Page ID
- 117412
En la Definición 1.4.5 definimos una combinación lineal de dos enteros\(a\) y\(b\) a un entero de la forma\(as+bt\). Si hacemos un seguimiento de las combinaciones lineales de dos enteros como\(9\) y\(24\), ¿qué vemos?
Evaluar\(9s+24t\) para varias opciones de números enteros\(s\) y\(t\), y realizar un seguimiento de los resultados, muestra que los números entre\(0\) y\(20\) que son combinaciones lineales de\(9\) y \(24\)son los siguientes:\[0, 3, 6, 9, 12, 15, 18.\nonumber \]
Una forma de comenzar a convencerse de esto podría ser notar eso\(3=9(-5) + 24(2)\), y luego multiplicar ambos lados de esta ecuación por enteros para obtener lo siguiente:\[\begin{aligned} 0 &= 9(0) + 24(0);\\ 3 &= 9(-5) + 24(2);\\ 6 &= 9(-10) + 24(4);\\ 9 &= 9(-15) + 24(6);\\ 12 &= 9(-20) + 24(8);\\ 15 &= 9(-25) + 24(10);\\ 18 &= 9(-30) + 24(12).\\\end{aligned}\] Continuar de esta manera le mostrará que cada múltiplo de 3 es una combinación lineal de\(9\) y \(24\). (¿Ves por qué las cosas que no son múltiplos de 3 no son combinaciones lineales de 9 y 24?)
Haciendo un trabajo similar para otros pares de 9 y otro número, podríamos ver que
- cada múltiplos de 9 son las combinaciones lineales de 0 y 9;
- cada número entero es una combinación lineal de 1 y 9;
- cada número entero es una combinación lineal de 2 y 9;
- los múltiplos de 3 son las combinaciones lineales de 3 y 9;
- cada número entero es una combinación lineal de 4 y 9;
- cada número entero es una combinación lineal de 5 y 9;
- los múltiplos de 3 son las combinaciones lineales de 6 y 9;
- cada número entero es una combinación lineal de 7 y 9;
- cada número entero es una combinación lineal de 8 y 9;
- los múltiplos de 9 son las combinaciones lineales de 9 y 9.
Aquí hay algunos patrones definidos. Primero, las combinaciones lineales de\(a\) y\(b\) siempre parecen ser exactamente el conjunto de múltiplos de algún entero positivo (observe que el conjunto de cada entero es exactamente el conjunto de múltiplos de 1).
A continuación, el número cuyos múltiplos forman las combinaciones lineales de\(a\) y\(b\) parece tener una relación especial con\(a\) y\(b\) —mirando los ejemplos anteriores, algo te puede destacar: las combinaciones lineales de \(a\)y\(9\) resulta ser exactamente el
- múltiplos de 9 si\(a\) es un múltiplo de 9,
- múltiplos de 3 si\(a\) es divisible por 3 pero no por 9, y
- múltiplos de 1 si no\(a\) es divisible por 3.
El siguiente teorema importante explica lo que hemos notado. También será crucial para las pruebas de algunos teoremas muy importantes en los próximos capítulos.
Para todos los enteros\(a\) y\(b\) existen enteros\(s\) y\(t\) tal que\[\gcd(a,b)=sa+tb.\nonumber \]
Además, si\(a\) o\(b\) es distinto de cero, entonces\(\gcd(a,b)\) es el entero positivo más pequeño que se puede escribir como\(sa + tb\), y las combinaciones lineales de\(a\) y\(b\) son precisamente los múltiplos de \(\gcd(a,b)\).
Prueba
Si\(a=b=0\) entonces\(s\) y\(t\) puede ser cualquier cosa desde\[\gcd(0,0)=0=s\cdot0+t\cdot0.\nonumber \] Entonces podemos suponer que\(a\ne 0\) o\(b\ne 0\). Let\[J=\{na+mb:n,m\in\mathbb{Z}\}.\nonumber \] Note que\(J\) contiene\(a\)\(-a\),,\(b\) y\(-b\) desde\[\begin{aligned} a &=1\cdot a+0 \cdot b; \\ -a &=(-1)\cdot a+0 \cdot b; \\ b &=0 \cdot a+1 \cdot b; \\ -b &=0 \cdot a+(-1) \cdot b.\end{aligned}\] Desde\(a\ne 0\) o\(b\ne 0\) uno de los elementos\(a\), \(-a\),\(b\),\(-b\) es positivo. Entonces podemos decir que\(J\) contiene algunos enteros positivos. Dejar\(S\) denotar el conjunto de enteros positivos en\(J\). Es decir,\[S=\{na+mb:na+mb>0,\,n,m\in\mathbb{Z}\}.\nonumber \]
Por el Principio de Ordenamiento Bien para\(\mathbb{N}\), sabemos que\(S\) contiene un entero positivo más pequeño; llamar a este entero\(d\). Demostremos eso\(d=\gcd(a,b)\).
Primero, mostramos que\(d\) es un divisor común de\(a\) y\(b\). Tenga en cuenta que ya\(d\in S\) tenemos\(d=sa+tb\) para algunos enteros,\(s\) y\(t\). Tenga en cuenta también eso\(d>0\). Para mostrar\(d\mid a\) usando el Algoritmo de División escribimos\(a=dq+r\) dónde\(0\le r<d\). Ahora\[\begin{aligned} r &=a-dq\\ &=a-(sa+tb)q\\ &=(1-sq)a+(-tq)b.\end{aligned}\] De ahí\(r\) es una combinación lineal de\(a\) y\(b\), y\(r\in J\). Si\(r>0\) entonces\(r\in S\). Pero esto no puede ser ya\(r<d\) y\(d\) es el entero más pequeño en\(S\). Entonces debemos tener\(r=0\). Es decir,\(a=dq\). De ahí\(d\mid a\). Por un argumento similar podemos demostrarlo\(d\mid b\). Por lo tanto,\(d\) es efectivamente un divisor común de\(a\) y\(b\).
Ahora demostramos que\(d\) es el mayor divisor común. Vamos\(e=\gcd(a,b)\). Entonces\(e\mid a\) y\(e\mid b\), así por el Teorema 1.4.1 (3),\(e\mid (sa+tb)\), es decir,\(e\mid d\). Desde\(e\) y\(d\) son positivos, por Teorema 1.4.1 (10), tenemos\(e\le d\). Por otro lado, ya que\(d\) es un divisor común de\(a\) y\(b\), eso también lo sabemos\(e \leq d\). De ahí\(d=\gcd(a,b)\).
Ahora supongamos que\(c\) es cualquier combinación lineal de\(a\) y\(b\). Por Teorema 1.4.1 (3), lo sabemos\(d \mid c\), así\(c\) es un múltiplo de\(d\). Por otro lado, si\(h\) es cualquier múltiplo de\(d\), entonces\(h=dk\) para algún número entero\(d\), y multiplicando ambos lados de la ecuación\(d = sa+tb\) por\(k\) rendimientos\[h = dk = (sk)a + (tk)b,\nonumber \] así \(h\)es de hecho una combinación lineal de\(a\) y\(b\). Por lo tanto, hemos demostrado que las combinaciones lineales de\(a\) y\(b\) son precisamente los múltiplos de\(\gcd(a,b)\).
\(1=\gcd(2,3)\)y tenemos\(1=(-1)2+1\cdot 3\). También tenemos\(1=2\cdot 2+(-1)3\). Entonces los números\(s\) y\(t\) en el Lema de Bezout no están determinados de manera única. De hecho, como veremos más adelante hay infinitamente muchas opciones para\(s\) y\(t\) para cada par\(a,b\).
La prueba anterior es un teorema de existencia. Afirma la existencia de\(s\) y\(t\), pero no proporciona una manera de encontrar realmente\(s\) y\(t\). También la prueba no da ninguna pista sobre cómo hacer el cálculo\(s\) y\(t\). Daremos dos algoritmos en el siguiente capítulo para encontrar\(s\) y\(t\).
Terminamos este capítulo con las dos primeras de varias consecuencias del Lema de Bezout, una sobre el mayor divisor común y la otra sobre el múltiplo menos común. Al igual que en la Sección 1.7, deje\(C(a,b)\) ser el conjunto de todos los divisores comunes de\(a\) y\(b\).
Cada elemento de\(C(a,b)\) divide\(\gcd(a,b)\).
Prueba
Si\(c\) es un divisor común de\(a\) y\(b\), entonces por el Teorema 1.4.1 (3),\(c\) divide cada combinación lineal de\(a\) y\(b\). Por Lema de Bezout,\(d\) es una combinación lineal de\(a\) y\(b\), entonces\(c \mid d\).
Si\(a\) y\(b\) son enteros positivos, entonces su mínimo común múltiplo satisface\[\operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}.\nonumber \]
Prueba
Dejemos\(q = \dfrac{ab}{\gcd(a,b)}\); nuestro objetivo es mostrar eso\(\operatorname{lcm}(a,b)=q\).
Dado que\(\gcd(a,b)\) es un divisor común de\(a\) y de\(b\), existen enteros\(v\) y\(w\) tal que\(a = v\gcd(a,b)\) y\(b=w\gcd(a,b)\). Entonces\[q = \frac{ab}{\gcd(a,b)}= bv=aw,\nonumber \] lo que demuestra que\(q\) es un múltiplo común de\(a\) y\(b\). Ya que\(\operatorname{lcm}(a,b)\) es el más pequeño de los múltiplos comunes positivos, tenemos eso\(\operatorname{lcm}(a,b) \leq q\).
Dado que\(\operatorname{lcm}(a,b)\) es un múltiplo común de\(a\) y\(b\), existen enteros\(j\) y\(k\) tal que\[\operatorname{lcm}(a,b)=ja=kb.\nonumber \] Por Lema de Bezout, existen enteros\(s\) y\(t\) tal \[\gcd(a,b) = as+bt.\nonumber \]Multiplicando ambos lados por\(\operatorname{lcm}(a,b)\) y recordando cómo\(j\)\(k\), y\(q\) se definen, encontramos\[\begin{aligned} \operatorname{lcm}(a,b)\gcd(a,b) &= as\operatorname{lcm}(a,b) + bt\operatorname{lcm}(a,b)\\ &= as(kb) + bt(ja)\\ &= (sk+tj)ab\\ &= (sk+tj)q\gcd(a,b). \end{aligned}\] Dividiendo ambos lados por\(\gcd(a,b)\) rendimientos\(\operatorname{lcm}(a,b) = (sk+tj)q\), así\(q\) divide\(\operatorname{lcm}(a,b)\). Esto implica que\(q \leq \operatorname{lcm}(a,b)\).
Desde\(\operatorname{lcm}(a,b) \leq q\) y\(\operatorname{lcm}(a,b) \geq q\), concluimos que\(\operatorname{lcm}(a,b)=q\), y la prueba es completa.
Ejercicios
Por ensayo y error, encuentre coeficientes\(s\) y\(t\) haga verdaderas las siguientes ecuaciones:
- \(60s + 35t = \gcd(60,35)\)
- \(42s + 28t = \gcd(42,28)\)
Encuentra tres pares diferentes de números enteros\(s,t\) que hagan la ecuación\(3s + 11t = 1\).
- Verdadero o falso, ¿y por qué? Si\(s\) y\(t\) son enteros y\(3s + 11t = 1\), entonces\(\gcd(s,t)=1\).
- Si\(s=9\) y\(t=-24\) y\(19s + 7t = 3\), ¿esto significa eso\(\gcd(19,7)=3\)? Ya sea que la respuesta sea sí o no, explique lo que dice el Lema de Bezout sobre los enteros 19 y 7.
Usando Proposición\(\PageIndex{1}\), computa lo siguiente.
- \(\operatorname{lcm}(803,154)\)
- \(\operatorname{lcm}(11,123)\)
- \(\operatorname{lcm}(2185,3059)\)
Según el número de Verano 2017 de QuadAngles, una publicación de la Asociación de Alumnos de la Universidad de Rhode Island, conocer tus múltiplos menos comunes y los mayores divisores comunes podría ayudarte a ingresar a la universidad en los primeros días de la Universidad:
Estos son los requisitos para ingresar al Rhode Island College of Agriculture and Mechanic Arts para septiembre de 1893. El Colegio había abierto el año anterior; esta es la prueba de admisión más temprana que pudimos encontrar.
ARITMÉTICO
1. Encuentra los L. C. M. y G. C. D. de 724 y 896....
Encuentra las respuestas a esta pregunta.
Vamos\(a>b>0\). Demostrar que si\(a=bq+r\), entonces\[\operatorname{lcm}(a,b)=\frac{a}{r}\operatorname{lcm}(b,r).\nonumber\] (Pista: Recordemos Lema 1.8.2.)