5.4: Los divisores comunes más grandes

Dados dos enteros cualesquiera\(a\) y\(b\), un entero\(c\neq0\) es un divisor común o factor común de\(a\) y\(b\) si\(c\) divide ambos\(a\) y\(b\). Si, además,\(a\) y no\(b\) son ambos iguales a cero, entonces el divisor común más grande, denotado por\(\gcd(a,b)\), se define como el divisor común más grande de\(a\) y\(b\). Los divisores más comunes también se denominan factores comunes más altos. Debe quedar claro que\(\gcd(a,b)\) debe ser positivo.

Ejemplo\(\PageIndex{1}\label{eg:gcd-01}\)

Los divisores comunes de 24 y 42 son\(\pm1\),\(\pm2\),\(\pm3\), y\(\pm6\). Entre ellos, 6 es el más grande. Por lo tanto,\(\gcd(24,42)=6\). Los divisores comunes de 12 y 32 son\(\pm1\),\(\pm2\) y\(\pm4\), se deduce que\(\gcd(12,32)=4\).

ejercicio práctico\(\PageIndex{1}\label{he:gcd-01}\)

Verifica eso\[\gcd(5,35)=5, \quad \gcd(-5,10)=5, \quad \gcd(20,-10)=10, \quad\mbox{and}\quad \gcd(20,70)=10. \nonumber\] Explica por qué\(\gcd(3,5)=1\)

Ejemplo\(\PageIndex{2}\label{eg:gcd-02}\)

¿Puedes explicar por qué\(\gcd(0,3)=3\)? ¿Qué tal\(\gcd(0,-3)=3\)?

Solución

Recordemos que 0 es divisible por cualquier entero distinto de cero. De ahí que todos los divisores de 3 sean también divisores de 0. Obviamente, 3 en sí es el divisor más grande de 3. Por lo tanto,\(\gcd(0,3)=3\).

ejercicio práctico\(\PageIndex{2}\label{he:gcd-02}\)

Explique por qué\(\gcd(0,-8)=8\).

Teorema\(\PageIndex{1}\label{thm:gcd0b}\)

Para cualquier entero distinto de cero\(b\), tenemos\(\gcd(0,b)=|b|\).

Prueba

El divisor positivo más grande de\(b\) es\(|b|\). Dado que\(|b|\) también divide 0, concluimos que\(\gcd(0,b)=|b|\).

El teorema 5.4.1 nos dice que\(\gcd(0,b)=|b|\) si\(b\) es distinto de cero. A partir de la definición de divisor común y máximo común divisor, es claro que\(\gcd(a,b) = \gcd(b,a)\), y\(\gcd(a,b) = \gcd(\pm a,\pm b)\). Entonces podemos asumir\(1\leq a\leq b\).

Teorema\(\PageIndex{2}\)

Dejar\(a\) y\(b\) ser enteros tales que\(1\leq a\leq b\). Si\(b=aq+r\), donde\(0\leq r< a\), entonces\(\gcd(b,a)=\gcd(a,r)\).

Prueba

Para facilitar nuestro argumento, vamos\(d=\gcd(b,a)\) y\(e=\gcd(a,r)\). Por definición,\(d\) es un divisor de ambos\(b\) y\(a\). Por lo tanto,\(b=dx\) y\(a=dy\) para algunos enteros\(x\) y\(y\). Entonces\[r = b-aq = dx-dy\cdot q = d(x-yq), \nonumber\] donde\(x-yq\) es un entero. De ahí,\(d\mid r\). Esto hace\(d\) un divisor común de ambos\(r\) y\(a\). Ya que\(e\) es el mayor divisor común de\(a\) y\(r\), lo determinamos\(d\leq e\).

De igual manera,\(e=\gcd(a,r)\) es un divisor de ambos\(a\) y\(r\). Así,\(a=eu\) y\(r=ev\) para algunos enteros\(u\) y\(v\). Entonces\[b = aq+r = a\cdot eu+ev = e(au+v), \nonumber\] donde\(au+v\) es un entero. De ahí,\(e\mid b\). Esto hace\(e\) un divisor común de ambos\(b\) y\(a\). Ya que\(d\) es el mayor divisor común de\(b\) y\(a\), deducimos eso\(e\leq d\). Junto con\(d\leq e\), concluimos que\(d=e\).

Ejemplo\(\PageIndex{3}\label{eg:gcd-03}\)

De\(997=996\cdot1+1\), obtenemos\(\gcd(997,996)=\gcd(996,1)=1\).

El teorema lo asegura\(\gcd(b,a) = \gcd(a,r)\). Podemos aplicar el teorema nuevamente a\(\gcd(a,r)\). Dividir\(a\) por\(r\) produce un nuevo cociente y un nuevo resto. Si es necesario, repita el proceso hasta que el resto se convierta en cero. Si denotamos\(b=r_0\) y\(a=r_1\), entonces De\[\begin{array}{rcl@{\qquad\qquad}l} r_0 &=& r_1 q_1 + r_2, & 0\leq r_2 < r_1, \\ r_1 &=& r_2 q_2 + r_3, & 0\leq r_3 < r_2, \\ r_2 &=& r_3 q_3 + r_4, & 0\leq r_4 < r_3, \\ \vdots & & \vdots \\ r_{k-1} &=& r_k q_k + r_{k+1}, & 0\leq r_{k+1} < r_k, \\ \vdots & & \vdots \\ r_{n-3} &=& r_{n-2} q_{n-2} + r_{n-1}, & 0\leq r_{n-1} < r_{n-2}, \\ r_{n-2} &=& r_{n-1} q_{n-1} + r_n, & r_n=0. \end{array} \nonumber\] ello se deduce que\[\gcd(b,a) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_{n-1},0) = r_{n-1}. \nonumber\] El último resto distinto de cero es\(\gcd(a,b)\). Este método para encontrar el divisor más común se llama algoritmo euclidiano.

Ejemplo\(\PageIndex{4}\label{eg:gcd-04}\)

Encuentra\(\gcd(426,246)\).

Solución

Al aplicar el teorema repetidamente, encontramos\[\begin{array}{rcl@{\qquad\qquad}lcl} 426 &=& 246\cdot1+180, & \gcd(426,246) &=& \gcd(246,180) \\ 246 &=& 180\cdot1+ 66, & \gcd(246,180) &=& \gcd(180, 66) \\ 180 &=& 66\cdot2+ 48, & \gcd(180, 66) &=& \gcd( 66, 48) \\ 66 &=& 48\cdot1+ 18, & \gcd( 66, 48) &=& \gcd( 48, 18) \\ 48 &=& 18\cdot2+ 12, & \gcd( 48, 18) &=& \gcd( 18, 12) \\ 18 &=& 12\cdot1+ 6, & \gcd( 18, 12) &=& \gcd( 12, 6) \\ 12 &=& 6\cdot2+ 0, & \gcd( 12, 6) &=& \gcd( 6, 0) = 6. \end{array} \nonumber\] Por lo tanto,\(\gcd(426,246)=6\).

ejercicio práctico\(\PageIndex{3}\label{he:gcd-03}\)

Determinar\(\gcd(732,153)\).

ejercicio práctico\(\PageIndex{4}\label{he:gcd-04}\)

Determinar\(\gcd(6958,2478)\).

A mano, es más eficiente usar un formato de dos columnas. Primero, pon los dos números 426 y 246 en dos columnas separadas, con el número mayor a la izquierda. Realiza una división corta y escribe el cociente a la izquierda:\[\begin{array}{r|r|r|r} 1 & 426 & 246 & \\ & 246 & & \\ \ \cline{2-2} & 180 & & \end{array} \nonumber\]

En la siguiente ronda, realizar otra división corta sobre los dos números 246 y 180 en la parte inferior. Dado que el número mayor se encuentra ahora en la columna de la derecha, deje el cociente a su derecha:

\[\begin{array}[t]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline & 180 & 66 & \end{array} \nonumber\]

Continuar de esta manera hasta que el resto se convierta en 0. La última entrada distinta de cero en la parte inferior es el divisor más común. También podemos dejar todos los cocientes a la izquierda:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \hline 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \hskip0.5in\mbox{or}\hskip0.5in \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & \\ 1 & 246 & 180 & \\ \hline 2 & 180 & 66 & \\ 1 & 132 & 48 & \\ \hline 2 & 48 & 18 & \\ 1 & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \nonumber\]

ejercicio práctico\(\PageIndex{5}\label{he:gcd-05}\)

Utilice el formato de dos columnas para calcular\(\gcd(153,732)\).

ejercicio práctico\(\PageIndex{6}\label{eg:gcd-06}\)

Utilice el formato de dos columnas para calcular\(\gcd(6958,2478)\).

Dado cualquier número entero\(m\) y\(n\), los números de la forma\(ms+nt\), donde\(s,t\) son enteros, se llaman las combinaciones lineales de\(m\) y\(n\). Desempeñan un papel importante en el estudio de\(\gcd(m,n)\), como se indica en el siguiente teorema.

Teorema\(\PageIndex{3}\)

Para cualquier número entero distinto de cero\(a\) y\(b\), existen enteros\(s\) y\(t\) tal que\(\gcd(a,b)=as+bt\).

Prueba

La prueba de este teorema es larga y complicada. Lo dejamos, junto con otros resultados relacionados, muchos de los cuales son bastante técnicos, a la siguiente sección.

Teorema\(\PageIndex{4}\)

Cada combinación lineal de\(a\) y\(b\) es un múltiplo de\(\gcd(a,b)\).

Corolario\(\PageIndex{5}\)

El mayor divisor común de dos enteros distintos de cero\(a\) y\(b\) es el entero positivo más pequeño entre todas sus combinaciones lineales.

Es importante entender lo que dicen estos tres resultados. Encontrar una combinación lineal de\(a\) y\(b\) solo nos da un múltiplo de\(\gcd(a,b)\). Sólo una combinación lineal especial producirá el valor exacto de\(\gcd(a,b)\).

Ejemplo\(\PageIndex{5}\label{eg:gcd-05}\)

Let\(n\) y\(n+1\) ser dos enteros positivos consecutivos. Entonces\[n\cdot(-1)+(n+1)\cdot1 = 1 \nonumber\] implica que 1 es un múltiplo del mayor divisor común de\(n\) y\(n+1\). Esto significa que el divisor más común debe ser 1. Por lo tanto,\(\gcd(n,n+1)=1\) para todos los enteros\(n\).

Definición

Dos enteros\(a\) y\(b\) se dice que son relativamente primos si\(\gcd(a,b)=1\). Por lo tanto,\(a\) y\(b\) son relativamente primos si no tienen divisores comunes excepto\(\pm 1\).

Ejemplo\(\PageIndex{6}\label{eg:gcd-06}\)

Demostrar que si\(\gcd(a,b)=1\), entonces\(\gcd(a+b,a-b)\) equivale a 1 o 2.

Solución

A partir de las combinaciones lineales\[\begin{aligned} (a+b)\cdot1+(a-b)\cdot1 &=& 2a, \\ (a+b)\cdot1+(a-b)\cdot(-1) &=& 2b, \end{aligned} \nonumber\] sabemos que\(\gcd(a+b,a-b)\) divide ambos\(2a\) y\(2b\). Ya que\(\gcd(a,b)=1\), concluimos que\(\gcd(a+b,a-b)\) divide 2. En consecuencia,\(\gcd(a+b,a-b)\) es 1 ó 2.

Ejemplo\(\PageIndex{7}\label{eg:gcd-07}\)

Mostrar que si\(\gcd(a,b)=1\), entonces\(\gcd(2a+b,a+2b)\) es igual a 1 o 3.

Solución

A partir de las combinaciones lineales\[\begin{aligned} (2a+b)\cdot 2 +(a+2b)\cdot(-1) &=& 3a, \\ (2a+b)\cdot(-1)+(a+2b)\cdot 2 &=& 3b, \end{aligned} \nonumber\] sabemos que\(\gcd(2a+b,a+2b)\) divide ambos\(3a\) y\(3b\). Ya que\(\gcd(a,b)=1\), concluimos que\(\gcd(2a+b,a+2b)\) divide 3. Así,\(\gcd(a+b,a-b)\) es 1 o 3.

ejercicio práctico\(\PageIndex{7}\label{he:gcd-07}\)

¿Cuáles son los posibles valores de\(\gcd(5m+7n,7m+5n)\) si los dos enteros positivos\(m\) y\(n\) son relativamente primos?

Ejemplo\(\PageIndex{8}\label{eg:gcd-08}\)

Encuentra los enteros\(s\) y\(t\) tal que\(6=\gcd(426,246)=246s+426t\).

Solución

Anteriormente, estudiamos cómo encontrar\(\gcd(426,246)=6\). En cada división, queremos expresar el resto como una combinación lineal de 246 y 426. Así es como procede el cómputo:

\[\begin{array}{lrcl} 426 = 246\cdot1+180,& 180 &=& 246\cdot(-1)+426\cdot1 \\ [3pt] 246 = 180\cdot1+66, & 66 &=& 246\cdot1+180\cdot(-1) \\ & &=& 246\cdot1+[246\cdot(-1)+426\cdot1]\cdot(-1) \\ & &=& 246\cdot2+426\cdot(-1) \\ [3pt] 180 = 66\cdot2+48, & 48 &=& 180\cdot1+66\cdot(-2) \\ & &=& [246\cdot(-1)+426\cdot1]\cdot1 +[246\cdot2+426\cdot(-1)]\cdot(-2) \\ & &=& 246(-5)+426\cdot3 \\ 66 = 48\cdot1+18, & 18 &=& 66\cdot1+48\cdot(-1) \\ & &=& [246\cdot2+426\cdot(-1)]\cdot1 + [246(-5)+426\cdot3]\cdot(-1) \\ & &=& 246\cdot7+426\cdot(-4) \\ [3pt] 48 = 18\cdot2+12, & 12 &=& 48\cdot1+18\cdot(-2) \\ & &=& [246(-5)+426\cdot3]\cdot1 + [246\cdot7+426\cdot(-4)]\cdot(-2) \\ & &=& 246\cdot(-19)+426\cdot11 \\ [3pt] 18 = 12\cdot1+6, & 6 &=& 18\cdot1 + 12\cdot(-1) \\ & &=& [246\cdot7+426\cdot(-4)]\cdot1 + [246\cdot(-19)+426\cdot11]\cdot(-1) \\ & &=& 246\cdot26+426\cdot(-15) \end{array} \nonumber\]

La respuesta es\(6=246\cdot26+426\cdot(-15)\).

¡El cómputo es tedioso! El algoritmo euclidiano extendido proporciona un alivio. Realiza un seguimiento de dos secuencias de enteros\(s_k\) y\(t_k\) junto con\(r_k\), tal que\[r_k = a s_k + b t_k. \nonumber\] Esto expresa cada resto como una combinación lineal de\(a\) y\(b\). Dado que el último resto distinto de cero es\(\gcd(a,b)\), la combinación lineal correspondiente será la respuesta que estamos buscando.

Los valores de\(s_k\) y\(t_k\) para el último ejemplo se resumen a continuación:

\[\begin{array}{|c|r|r|r| } \hline k & r_k & s_k & t_k \\ \hline 2 & 180 & -1 & 1 \\ 3 & 60 & 2 & -1 \\ 4 & 48 & -5 & 3 \\ 5 & 18 & 7 & -4 \\ 6 & 12 & -19 & 11 \\ 7 & 6 & 26 & -15 \\ \hline \end{array} \nonumber\]

El problema principal es: ¿cómo podemos calcular estos valores de manera eficiente?

La tabla anterior comienza con\(k=2\). ¿Qué tal\(k=0\) y\(k=1\)? A partir de\[b = r_0 = a s_0 + b t_0, \nonumber\] determinamos que\(s_0=0\) y\(t_0=1\). Del mismo modo,

\[a = r_1 = a s_1 + b t_1 \nonumber\]

implica que\(s_1=1\) y\(t_1=0\). De ahí que la lista de valores de\(s_k\) y\(t_k\) comience con lo siguiente:

\[\begin{array}{ccc} k & s_k & t_k \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \nonumber\]

En general, antes de llevar a cabo la división\(r_{k-1}\div r_k\), deberíamos haber generado ya\(s_0\) a través\(s_k\), y\(t_0\) a través\(t_k\). Después de la división, obtenemos\(q_k\) y\(r_{k+1}\) como en

\[r_{k-1} = r_k q_k + r_{k+1}. \nonumber\]

A continuación, calculamos\(s_{k+1}\) y\(t_{k+1}\) antes de pasar a la siguiente división. ENCONTRAMOS

\[\begin{array}{rcl} r_{k+1} &=& r_{k-1} - r_k q_k \\ &=& (a s_{k-1} + bt_{k-1}) - (a s_k + b t_k) q_k \\ &=& a (s_{k-1} - s_k q_k) + b (t_{k-1} - t_k q_k). \end{array} \nonumber\]

Por lo tanto, necesitamos

\[\begin{array}{r c l} s_{k+1} &=& s_{k-1} - s_k q_k, \\ t_{k+1} &=& t_{k-1} - t_k q_k. \end{array} \nonumber\]

En palabras:

\[\displaylines{ \mbox{next $s$-value} = \mbox{previous-previous $s$-value} - \mbox{previous $s$-value}\times \mbox{corresponding $q$}, \cr \mbox{next $t$-value} = \mbox{previous-previous $t$-value} - \mbox{previous $t$-value}\times \mbox{corresponding $q$}. \cr} \nonumber\]

Por ejemplo, supongamos en una determinada etapa, los valores de\(s\)\(t\), y\(q\) son los siguientes:

\[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ & & & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\]Entonces\[\displaylines{ \mbox{next $s$-value} = -1-2\cdot2 = -5, \cr \mbox{next $t$-value} = 1-(-1)\cdot2 = 3. \cr} \nonumber\] Ahora la lista se convierte\[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ 4 & -5 & 3 & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\]

Todo el cálculo se puede llevar a cabo en un formato modificado de dos columnas.

Ejemplo\(\PageIndex{9}\label{eg:gcd-09}\)

Encuentra enteros\(s\) y\(t\) tal que\(\gcd(246,426)=246s+426t\).

Solución

Primero, copie los cocientes de la columna más a la derecha e insértelos entre esos cocientes en la columna más a la izquierda:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \qquad\mbox{becomes}\qquad \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ 1 & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ 1 & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ 1 & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \nonumber\]

A continuación, compute\(s_k\) y\(t_k\) junto a estos cocientes (no necesitamos registrar los valores de\(k\)):

\[\begin{array}[t]{rr@{\qquad}r|r|r|r} s_k & t_k & \multicolumn{1}{r}{q_k} \\ 0 & 1 \\ 1 & 0 & 1 & 426 & 246 & 1 \\ -1 & 1 & 1 & 246 & 180 & \\ \cline{4-5} 2 & -1 & 2 & 180 & 66 & 1 \\ -5 & 3 & 1 & 132 & 48 & \\ \cline{4-5} 7 & -4 & 2 & 48 & 18 & 1 \\ -19 & 11 & 1 & 36 & 12 & \\ \cline{4-5} 26 & -15 & 2 & 12 & 6 & \\ & & & 12 & & \\ \cline{4-4} & & & 0 & \end{array} \nonumber\]El último resto distinto de cero es el divisor más común, y la última combinación lineal da la respuesta deseada. Nos encontramos\(\gcd(246,426) = 6 = 26\cdot246-15\cdot426\).

Observe que, comenzando con\(k=2\), los signos de\(s_k\) y\(t_k\) alternar. Esto proporciona una revisión rápida de sus señales. Además, los signos de\(s_k\) y\(t_k\) son opuestos para cada uno\(k\geq2\).

ejercicio práctico\(\PageIndex{8}\label{he:gcd-08}\)

Utilice el formato de dos columnas para encontrar la combinación lineal que produce\(\gcd(153,732)\).

ejercicio práctico\(\PageIndex{9}\label{he:gcd-09}\)

Utilice el formato de dos columnas para encontrar la combinación lineal que produce\(\gcd(2478,6958)\).

Resumen y revisión

• El mayor divisor común de dos enteros, no ambos cero, es el entero más grande (de ahí que deba ser positivo) que divide ambos.
• Usa el algoritmo euclidiano para encontrar el divisor más común. Se puede implementar en un formato de dos columnas.
• Usando una versión extendida con dos columnas adicionales para computación\(s_k\) y\(t_k\), podemos encontrar la combinación lineal especial de dos enteros que produce su mayor divisor común.
• En general, una combinación lineal de dos enteros sólo da un múltiplo de su mayor divisor común.

Ejercicio\(\PageIndex{1}\label{ex:gcd-01}\)

Para cada uno de los siguientes pares de enteros, encuentre la combinación lineal que sea igual a su divisor más común.

1. 27, 81
2. 24, 84
3. 1380, 3020

Ejercicio\(\PageIndex{2}\label{ex:gcd-02}\)

Para cada uno de los siguientes pares de enteros, encuentre la combinación lineal que sea igual a su divisor más común.

1. 120, 615
2. 412, 936
3. 1122, 3672

Ejercicio\(\PageIndex{3}\label{ex:gcd-03}\)

¿Cuáles son los valores posibles de\(\gcd(2a+5b,5a-2b)\) si los dos enteros positivos aa y bb son relativamente primos?

Ejercicio\(\PageIndex{4}\label{ex:gcd-04}\)

Demostrar que cualquier número entero positivo impar consecutivo es relativamente primo.

Ejercicio\(\PageIndex{5}\label{ex:gcd-05}\)

Dejar\(m\) y\(n\) ser enteros positivos. Demostrar eso\(\gcd(m,m+n)\mid n\).

Ejercicio\(\PageIndex{6}\label{ex:gcd-06}\)

Dejar\(a\) y\(b\) ser enteros tales que\(1<a<b\) y\(\gcd(a,b)=1\). Demostrar eso\(\gcd(a+b,ab)=1\).

Ejercicio\(\PageIndex{7}\label{ex:gcd-07}\)

¿Cuáles son los posibles valores de\(\gcd(3m-5n,5m+3n)\) si los dos enteros positivos\(m\) y\(n\) son relativamente primos?

Ejercicio\(\PageIndex{8}\label{ex:gcd-08}\)

¿Cuáles son los posibles valores de\(\gcd(4p+7q,7p-4q)\) si los dos enteros positivos\(p\) y\(q\) son relativamente primos?