1.5: El mayor divisor común
- Page ID
- 115005
En esta sección definimos el mayor divisor común (gcd) de dos enteros y discutimos sus propiedades. También demostramos que el mayor divisor común de dos enteros es una combinación lineal de estos enteros.
Dos enteros\(a\) y\(b\), no ambos\(0\), pueden tener sólo finitamente muchos divisores, y así solo pueden tener finitamente muchos divisores comunes. En esta sección, nos interesa el mayor divisor común de\(a\) y\(b\). Tenga en cuenta que los divisores de\(a\) y el de\(\mid a \mid\) son los mismos.
El mayor divisor común de dos enteros\(a\) y\(b\) es el mayor entero que divide ambos\(a\) y\(b\).
Denotamos el mayor divisor común de dos enteros\(a\) y\(b\) por\((a,b)\). También definimos\((0,0)=0\).
Obsérvese que el mayor divisor común de 24 y 18 es 6. En otras palabras\((24,18)=6\).
Hay parejas de enteros (por ejemplo, 3 y 4, etc...) cuyo divisor más común es 1 así que llamamos a tales enteros enteros relativamente primos.
Dos enteros\(a\) y\(b\) son relativamente primos si\((a,b)=1\).
El divisor más común de 9 y 16 es 1, así que son relativamente primos.
Tenga en cuenta que cada entero tiene divisores positivos y negativos. Si\(a\) es un divisor positivo de\(m\), entonces también\(-a\) es un divisor de\(m\). Por lo tanto, por nuestra definición del mayor divisor común, podemos verlo\((a,b)=(\mid a\mid, \mid b\mid)\).
Presentamos ahora un teorema sobre el mayor divisor común de dos enteros. El teorema afirma que si dividimos dos enteros por su mayor divisor común, entonces el resultado es un par de enteros que son relativamente primos.
Si\((a,b)=d\) entonces\((a/d,b/d)=1\).
Eso lo demostraremos\(a/d\) y no\(b/d\) tenemos divisores positivos comunes que no sean\(1\). Supongamos que\(k\) es un divisor común positivo tal que\(k\mid a/d\) y\(k\mid b/d\). Como resultado, hay dos enteros positivos\(m\) y\(n\) tal que\[a/d=km \hspace{0.3 cm}\mbox{and} \ \ b/d=kn\] Así obtenemos que De\[a=kmd \hspace{0.3 cm}\mbox{and} \ \ b=knd.\] ahí\(kd\) es un divisor común de ambos\(a\) y\(b\). También,\(kd\geq d\). Sin embargo,\(d\) es el mayor divisor común de\(a\) y\(b\). Como resultado, eso lo conseguimos\(k=1\).
El siguiente teorema muestra que el mayor divisor común de dos enteros no cambia cuando agregamos un múltiplo de uno de los dos enteros al otro.
Dejar\(a,b\) y\(c\) ser enteros. Entonces\((a,b)=(a+cb,b)\).
Mostraremos que cada divisor de\(a\) y también\(b\) es un divisor de\(a+cb\)\(b\) y y viceversa. De ahí que tengan exactamente los mismos divisores. Entonces obtenemos que el mayor divisor común de\(a\) y también\(b\) será el mayor divisor común de\(a+cb\) y\(b\). Que\(k\) sea un divisor común de\(a\) y\(b\). Por teorema [thm4],\(k \mid (a+cb)\) y por lo tanto\(k\) es un divisor de\(a+cb\). Ahora supongamos que\(l\) es un divisor común de\(a+cb\) y\(b\). También por Teorema [thm4] tenemos,\[l\mid ((a+cb)-cb)=a.\] Como resultado,\(l\) es un divisor común de\(a\) y\(b\) y el resultado sigue.
Observe eso\((4,14)=(4,14-3\cdot 4)=(4,2)=2\).
Presentamos ahora un teorema que demuestra que el mayor divisor común de dos enteros puede escribirse como una combinación lineal de los dos enteros.
[thm9] El mayor divisor común de dos enteros\(a\) y\(b\), no ambos\(0\) es el menor número entero positivo tal que\(ma+nb=d\) para algunos enteros\(m\) y\(n\).
Asumir sin pérdida de generalidad que\(a\) y\(b\) son enteros positivos. Considere el conjunto de todas las combinaciones lineales de enteros positivos de\(a\) y\(b\). Este conjunto ya no está vacío\(a=1\cdot a+0\cdot b\) y ambos\(b=0\cdot a+1\cdot b\) están en este conjunto. Por lo tanto, este conjunto tiene un elemento mínimo\(d\) por el principio de ordenamiento adecuado. Así,\(d=ma+nb\) para algunos enteros\(m\) y\(n\). Tenemos que demostrar que\(d\) divide ambos\(a\) y\(b\) y que es el mayor divisor de\(a\) y\(b\).
Por el algoritmo de división, tenemos\[a=dq+r, \ \ \ 0\leq r<d.\] Así tenemos\[r=a-dq=a-q(ma+nb)=(1-qm)a-qnb.\] Tenemos entonces que\(r\) es una combinación lineal de\(a\) y\(b\). Dado que\(0\leq r<d\) y\(d\) es el número entero menos positivo que es una combinación lineal de\(a\) y\(b\), entonces\(r=0\) y\(a=dq\). De ahí\(d\mid a\). De igual manera\(d\mid b\). Ahora fíjense que si hay un divisor\(c\) que divide ambos\(a\) y\(b\). Luego\(c\) divide cualquier combinación lineal de\(a\) y\(b\) por Teorema 4. De ahí\(c\mid d\). Esto prueba que cualquier divisor común de\(a\) y\(b\) divide\(d\). De ahí\(c\leq d\), y\(d\) es el mayor divisor.
Como resultado, concluimos que si\((a,b)=1\) entonces existen enteros\(m\) y\(n\) tal que\(ma+nb=1\).
Seamos\(a_1,a_2,...,a_n\) enteros, no todos\(0\). El mayor divisor común de estos enteros es el entero más grande que divide todos los enteros en el conjunto. El mayor divisor común de\(a_1,a_2,...,a_n\) se denota por\((a_1,a_2,...,a_n)\).
Se dice que los números enteros\(a_1,a_2,...,a_n\) son mutuamente primos relativamente si\((a_1,a_2,...,a_n)=1\).
Los enteros\(3, 6, 7\) son mutuamente relativamente primos ya que\((3,6,7)=1\) aunque\((3,6)=3\).
Los enteros\(a_1,a_2,...,a_n\) se llaman primos por pares si para cada uno\(i\neq j\), tenemos\((a_i,a_j)=1\).
Los números enteros\(3,14,25\) son pares relativamente primos. Observe también que estos números enteros son mutuamente primos relativamente.
Observe que si\(a_1,a_2,...,a_n\) son pares relativamente primos, entonces son mutuamente relativamente primos.
Ejercicios
- Encuentra el mayor divisor común de 15 y 35.
- Encuentra el mayor divisor común de 100 y 104.
- Encuentra el mayor divisor común de -30 y 95.
- Dejar\(m\) ser un entero positivo. Encuentra el mayor divisor común de\(m\) y\(m+1\).
- Dejar\(m\) ser un entero positivo, encontrar el mayor divisor común de\(m\) y\(m+2\).
- Mostrar que si\(m\) y\(n\) son enteros tales que\((m,n)=1\), entonces (m+n, m-n) =1 o 2.
- Mostrar que si\(m\) es un entero positivo, entonces\(3m+2\) y\(5m+3\) son relativamente primos.
- Mostrar que si\(a\) y\(b\) son números enteros primos relativamente, entonces\((a+2b,2a+b)=1\) o\(3\).
- Mostrar que si\(a_1,a_2,...,a_n\) son enteros que no son todos 0 y\(c\) es un entero positivo, entonces\((ca_1,ca_2,...,ca_n)=c(a_1,a_2,...a_n).\)