1.7: Divisor común más grande y múltiplo mínimo común
- Page ID
- 117462
En los últimos capítulos hemos discutido la divisibilidad y el Algoritmo de División cuando un solo número se divide por otro. En este capítulo comenzamos a observar divisores y múltiplos que dos números tienen en común.
Vamos\(a,b\in\mathbb{Z}\). Si\(a\ne 0\) o\(b\ne 0\), definimos el mayor divisor común de\(a\) y\(b\), denotado\(\gcd(a,b)\), para ser el entero más grande\(d\) tal que\(d\mid a\) y \(d\mid b\). Definimos\(\gcd(0,0)=0\).
Discusión.
Si\(e\mid a\) y\(e\mid b\) llamamos\(e\) un divisor común de\(a\) y\(b\). \[C(a,b)=\{e:e\mid a\text{ and }e\mid b\},\nonumber \]Que sea,\(C(a,b)\) es el conjunto de todos los divisores comunes de\(a\) y\(b\). Tenga en cuenta que ya que todo se divide\(0\)\[C(0,0)=\mathbb{Z}\nonumber \] por lo que no hay un divisor común más grande de\(0\) con\(0\). Es por ello que debemos definir\(\gcd(0,0)=0\).
\[C(18,30)=\{-1,1,-2,2,-3,3,-6,6\}.\nonumber\]Entonces\(\gcd(18,30)=6\).
Si\(e\mid a\) entonces\(-e\mid a\).
Prueba
Si\(e\mid a\) entonces\(a=ek\) para algunos\(k\). Entonces\(a=(-e)(-k)\). Ya que\(-e\) y también\(-k\) son enteros\(-e\mid a\).
Si\(a\ne 0\), el entero positivo más grande que divide\(a\) es\(|a|\).
Prueba
Recordemos que\[|a|=\left\{\begin{array}{ccc} a & \text{if} & a\ge 0 \\ -a & \text{if} & a<0. \end{array}\right.\nonumber \] Primera nota que\(|a|\) en realidad divide\(a\): Si\(a>0\), ya que\(a\mid a\) sabemos que tenemos\(|a|\mid a\). Si\(a<0\),\(|a|=-a\). En este caso\(a=(-a)(-1)=|a|(-1)\) así\(|a|\) es un factor de\(a\). Entonces, en cualquier caso\(|a|\) divide\(a\), y en cualquiera de los dos casos\(|a|>0\), ya que\(a\ne 0\).
Ahora supongamos\(d\mid a\) y\(d\) es positivo. Entonces\(a=dk\) algunos\(k\) así\(-a=d(-k)\) para algunos\(k\). Entonces\(d\mid |a|\). Entonces por Teorema 1.4.1 (10) tenemos\(d\le|a|\).
El siguiente lema muestra que en\(\gcd\) la computación podemos limitarnos al caso donde ambos enteros son positivos.
Para cualquier número entero\(a\) y\(b\),\[\gcd(a,b)=\gcd(|a|,|b|).\nonumber \]
Prueba
Si\(a=0\) y\(b=0\), tenemos\(|a|=a\) y\(|b|=b\). Entonces\(\gcd(a,b)=\gcd(|a|,|b|)\). Supongamos que uno de\(a\) o no lo\(b\) es\(0\). Tenga en cuenta que\(d\mid a\Leftrightarrow d\mid |a|\). Ver Ejercicio\(\PageIndex{1}\). De ello se deduce que\[C(a,b)=C(|a|,|b|).\nonumber \] Así que el divisor común más grande de\(a\) y\(b\) es también el divisor común más grande de\(|a|\) y\(|b|\).
El último lema anterior mostró que para encontrar el mayor divisor común de dos números cualesquiera, es suficiente para poder hacerlo para números no negativos. El ejercicio\(\PageIndex{1}\) al final del capítulo prueba una afirmación más general sobre la divisibilidad.
Para cualquier número entero\(a\) y\(b\),\[\gcd(a,b)=\gcd(b,a).\nonumber \]
Prueba
Claramente\(C(a,b)=C(b,a)\). De ello se deduce que el entero más grande en\(C(a,b)\) es el entero más grande en\(C(b,a)\), es decir,\(\gcd(a,b)=\gcd(b,a)\).
Si\(a\ne 0\) y\(b\ne 0\), entonces\(\gcd(a,b)\) existe y satisface\[0<\gcd(a,b)\le\min\{|a|,|b|\}.\nonumber \]
Prueba
Tenga en cuenta que\(\gcd(a,b)\) es el entero más grande en el conjunto\(C(a,b)\) de división común de\(a\) y\(b\). Desde\(1\mid a\) y eso lo\(1\mid b\) sabemos\(1\in C(a,b)\). Por lo que el divisor común más grande debe ser al menos\(1\) y por lo tanto es positivo. Por otro lado\(d\in C(a,b)\Rightarrow d\mid |a|\) y\(d\mid |b|\) así no\(d\) es mayor que\(|a|\) y no mayor que\(|b|\). Así\(d\) es como mucho el más pequeño de\(|a|\) y\(|b|\). De ahí\(\gcd(a,b)\le\min\{|a|,|b|\}\).
De los lemas anteriores tenemos También\[\begin{split} \gcd(48,732) &=\gcd(-48,732) \\ &=\gcd(-48,-732) \\ &=\gcd(48,-732). \end{split}\] sabemos que\[0<\gcd(48,732)\le 48.\nonumber \] Ya que si\(d=\gcd(48,732)\), entonces\(d\mid 48\), para encontrar\(d\) podemos comprobar sólo qué divisores positivos de\(48\) también dividen\(732\).
En el siguiente capítulo discutiremos una forma más práctica computacionalmente de cómputos\(\gcd(a,b)\). En este momento discutimos un concepto complementario.
Vamos\(a,b\in\mathbb{N}\). Definimos el mínimo común múltiplo de\(a\) y\(b\), denotado\(\operatorname{lcm}(a,b)\), para ser el entero positivo más pequeño\(m\) tal que\(a\mid m\) y\(b\mid m\).
Si deseamos encontrar\(\operatorname{lcm}(6,10)\), podemos comenzar enumerando múltiplos positivos de 10 y buscando el primero que divisible por 6. Como ni 10 ni 20 es divisible por 6 sino\(30 = 10 \cdot 3 = 6 \cdot 5\), vemos tanto que 30 es un múltiplo de ambos 6 como de 10, y ningún múltiplo positivo menor de 10 es divisible por 6. De ahí\(\operatorname{lcm}(6,10)=30\).
Ejercicios\(\PageIndex{5}\) y \(\PageIndex{6}\)en este capítulo te invitan a descubrir algunas propiedades básicas de\(\operatorname{lcm}(a,b)\). Al igual que el mayor divisor común, el múltiplo menos común se desarrollará aún más en los próximos capítulos.
Ejercicios
Demostrar eso\[d\mid a\Leftrightarrow d\mid |a|.\nonumber \] (Pista: recuerda que\[|a|=\begin{cases}a & \text{ if } a\ge 0;\\-a & \text{ if } a<0\end{cases},\nonumber \] por lo que puede ayudar considerar dos casos. También recuerda la definición de “divide”, y úsela aquí.)
Encontrar\(\gcd(48,732)\) usando Ejemplo\(\PageIndex{2}\).
Encuentra\(\gcd(a,b)\) para cada uno de los siguientes valores de\(a\) y\(b\):
- \(a=-14\),\(b=14\)
- \(a=-1\),\(b=78654\)
- \(a=0\),\(b=-78\)
- \(a=2\),\(b=-786541\)
Encuentra ambos\(\gcd(a,b)\) y\(\operatorname{lcm}(a,b)\) para cada uno de los siguientes valores de\(a\) y\(b\). (Explique su razonamiento, utilizando únicamente las definiciones y propiedades discutidas en este capítulo; no asuma otras propiedades que aún no hayan sido probadas).
- \(a=3\),\(b=14\)
- \(a=9\),\(b=15\)
- \(a = 58\),\(b=406\)
- \(a=74\),\(b=111\)
La definición que se da en este capítulo requiere que\(\operatorname{lcm}(a,b)\) sea un entero positivo y eso\(a\) y\(b\) sean números naturales. Para examinar por qué esto podría ser conveniente, responda lo siguiente:
- ¿Cuál es el múltiplo común más pequeño (no necesariamente positivo) de\(0\) y\(b\), dónde\(b\) está algún entero?
- Si ni\(a\) ni lo\(b\) es\(0\), ¿existe un múltiplo común más pequeño de\(a\) y\(b\) entre los enteros negativos? Ilustra tu respuesta con un ejemplo, eligiendo un par específico\(a,b\) de enteros distintos de cero y discutiendo sus múltiplos comunes.
Cada uno de los lemas de este capítulo discute divisores y/o\(\gcd(a,b)\). Por cada lema, ¿puedes encontrar una afirmación similar, verdadera sobre múltiplos y/o\(\operatorname{lcm}(a,b)\)? Si es así, anote estas declaraciones (probarlas es alentada pero optativa); si no, explica por qué no.