Seminario de Resolución de Problemas: Máximo común divisor

Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.

Divisibilidad y máximo común divisor

Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.

Decimos que $a$ divide a $b$ si $b$ es un mútiplo de $a$ , es decir, si existe un $r$ tal que $b=ra$ . Lo escribimos en símbolos como $a\mid b$ . También decimos que $a$ es divisor de $b$ .

Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si $a\mid b$ y $b\mid a$ , entonces $|a|=|b|$ , es decir $a=b$ o $a=-b$ .

Si tenemos varios números $a_1,\ldots,a_n$ , el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por $\MCD{a_1,\ldots,a_n}$ y $\mcm{a_1,\ldots,a_n}$ .

Proposición 2. Si $n$ divide a $a$ y a $b$ , entonces divide a cualquier combinación lineal entera $ra+sb$ de ellos. En particular, si $n$ divide a dos términos de la igualdad $a+b=c$ , entonces divide al tercero.

Notemos que $a+(b-a)=b$ . Por la Proposición 2, un divisor de $a$ y $b$ será divisor de $b-a$ , y uno de $b-a$ y de $a$ será divisor de $b$ . De aquí sale que $\MCD{a,b}=\MCD{a,b-a}$

Problema. Determina todas las funciones $f:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{Z}^+$ tales que cumplen las siguientes tres propiedades simultáneamente:

$f(a,a)=a$ para todo entero positivo $a$ .
$f(a,b)=f(b,a)$ para todo par de enteros positivos $a$ y $b$ .
$f(a,b)=f(a,a+b)$ para todo par de enteros positivos $a$ y $b$ .

Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de $f(a,b)$ para todos $a$ y $b$ enteros positivos. Intenta probar tu conjetura por inducción fuerte.

Solución. Vamos a mostrar que $f(a,b)=\MCD{a,b}$ para todo par de enteros positivos $a$ y $b$ . Vamos a probarlo por inducción sobre la suma $a+b$ . Como $a$ y $b$ son enteros positivos, la menor suma que pueden tener es $2$ y en este caso $a+b=2$ implica $a=b=1$ . Por la hipótesis 1, tenemos $f(1,1)=1$ , que coincide con $\MCD{1,1}$ .

Supongamos que el resultado es cierto cuando $a+b=k$ para todo entero $k=1,\ldots,n$ y tomemos $a$ y $b$ enteros de suma $n+1$ . Si $a=b$ , entonces

$f(a,b)=f(a,a)=a=\MCD{a,a}=\MCD{a,b},$

como queremos. Si $a\neq b$ , por la simetría que nos da la hipótesis 2 podemos suponer $b>a$ . Por la hipótesis 3,

$f(a,b)=f(a,a+(b-a))=f(a,b-a).$

En la expresión de la derecha, tenemos que sus entradas suman $a+(b-a)=b<a+b=n+1$ , de modo que podemos aplicar la hipótesis inductiva para obtener que $f(a,b-a)=\MCD{a,b-a}$ . Por la discusión antes de este problema, $\MCD{a,b-a}=\MCD{a,b}$ . Así, concluimos que $f(a,b)=\MCD{a,b}$ , como queríamos.

$\square$

El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.

Proposición 3. Si tenemos otro número $d$ que sea divisor de $a_1,\ldots,a_n$ , entonces

$d\mid \MCD{a_1,\ldots,a_n}.$

Si tenemos otro número $M$ que sea múltiplo de $a_1,\ldots,a_n$ , entonces

$\mcm{a_1,\ldots,a_n}\mid M.$

Problema. Sean $a$ y $b$ enteros positivos. Muestra que

$\MCD{a,b}\mcm{a,b}=ab.$

Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.

Solución. Para simplificar la notación, tomamos $D=\MCD{a,b}$ y $m=\mcm{a,b}$ .

Como $D$ divide a $a$ y $b$ , existen enteros $r$ y $s$ tales que $a=rD$ y $b=sD$ . Notemos que $rsD=as=br$ , así que $rsD$ es un múltiplo de $a$ y $b$ , y por la Proposición 3, tenemos que $m\mid rsD$ . Multiplicando por $D$ esta divisibilidad, tenemos que $Dm\mid rsD^2=ab$ .

Como $ab$ es múltiplo de $a$ y de $b$ , por la Proposición $3$ es múltiplo de $m$ , digamos $ab=km$ . Notemos que de aquí, tenemos $a=k(m/b)$ con $m/b$ entero y $b=k(m/a)$ con $m/a$ entero, de modo que $k$ divide a $a$ y a $b$ . Como $D$ es máximo común divisor, por la Proposición 3 tenemos que $k\mid D$ . Multiplicando por $m$ esta divisibilidad, tenemos que $km\mid DM$ , es decir, $ab\mid Dm$ .

Con esto logramos conseguir que $ab\mid Dm$ y $Dm\mid ab$ . Por la Proposición $1$ , tenemos que $|ab|=|Dm|$ , pero como $a$ , $b$ , $D$ , $m$ son positivos, entonces $ab=Dm$ .

$\square$

Algoritmo de la división y algoritmo de Euclides

Tomemos $a$ y $b$ enteros. Si intentamos expresar a $a$ como múltiplo de $b$ , puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo “pequeño”. Esto es lo que dice el algoritmo de la división.

Teorema 1 (Algoritmo de la división). Para enteros $a$ y $b\neq 0$ , existen únicos enteros $q$ y $r$ tales que $0\leq r < |b|$ y $a=bq+r$ .

Consideremos la igualdad $a=bq+r$ en el algoritmo de la división y apliquemos la Proposición 2. Si $d$ divide a $a$ y $b$ , entonces divide a $r$ . Si $d$ divide a $r$ y a $b$ , entonces divide a $a$ . Así, $\MCD{a,b}=\MCD{b,r}$ , en donde $b$ y $r$ ahora son números más chicos que $a$ y $b$ . De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades

$\begin{align*}a&=bq_1+r_1\\b&=r_1 q_2 + r_2\\r_1&= r_2q_3 + r_3\\&\vdots\\r_{n-2}&= r_{n-1}q_n + r_n\\r_{n-1}&= r_nq_{n+1} + 0\\ \end{align*}$

de las que obtenemos

$\MCD{a,b}=\MCD{b,r_1}=\ldots=\MCD{r_n,0}=r_n.$

En las igualdades llegamos a un residuo $0$ pues $b>r_1>r_2>r_3>\ldots\geq 0$ es una sucesión estrictamente decreciente de enteros no negativos.

En particular, obtenemos

$\MCD{a,b}=r_n.$

A esto se le conoce como el algoritmo de Euclides, que enunciamos en otras palabras a continuación.

Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de $a$ y $b$ aplicando el algoritmo de la división a $a$ y $b$ , a $b$ y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es $\MCD{a,b}$ .

Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.

Problema. Sean $a\geq b$ enteros. Sean $q_i$ y los $r_i$ los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de $n+1$ vectores en $\mathbb{R}^3$ como sigue:

$\begin{align*}v_1&=(a,1,0)\\v_2&=(b,0,2)\\v_{i+2}&=v_{i}-q_iv_{i+1}\quad \text{para $i=1,\ldots,n-1$}\end{align*}$

Sean $r_{-1}=a$ y $r_{0}=b$ . Muestra que para $i=1,2,3,\ldots,n+1$ se tiene que $v_i=(x_i,y_i,z_i)$ , en donde:

$x_i=r_{i-2}$
$x_i=ay_i+bz_i$

Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos $i=1,2$ son inmediatos.

Solución. Procedemos por inducción fuerte en el subíndice $i$ . Para $i=1,2$ , el resultado es cierto pues $x_1=a=r_{-1}$ , $x_2=b=r_0$ , $a=1\cdot a + 0 \cdot b$ y $b=0 \cdot a + 1\cdot b$ . Supongamos el resultado cierto para los índices $1,2,\ldots, k$ para algún $2\leq k\leq n$ . Tomemos el índice $k+1$ .

Estudiemos primero la entrada $x_{k+1}$ . Por definición de la recursión e hipótesis inductiva

$\begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=r_{k-3}-q_{k-1}r_{k-2}\\&=r_{k-1},\end{align*}$

que es lo que queríamos mostrar para la entrada $x_{k+1}$ . Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que

$\begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=ay_{k-1}+bz_{k-1} - q_{k-1} (ay_{k}+bz_{k})\\&=a(y_{k-1}-q_{k-1}y_k) + b(z_{k-1}-q_{k-1}z_k)\\&=ay_{k+1}+bz_{k+1}.\end{align*}$

Con esto terminamos la inducción.

$\square$

El problema anterior nos dice que, en particular, $r_n=ay_n+bx_n$ . Esta conclusión es muy importante y la enunciamos como teorema.

Teorema 3. El máximo común divisor de enteros $a$ y $b$ se puede escribir como combinación lineal entera de $a$ y $b$ , es decir, existen enteros $m$ y $n$ tales que $\MCD{a,b}=am+bn$ .

Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.

Problema. Expresa al máximo común divisor de $754$ y $221$ como combinación lineal entera de estos números.

Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones $2,3,4$ ). En el primer rengón vamos apuntando las $q_i$ .

		3	2	2	3
754	221	91	39	13	0
1	0	1	-2	5	-17
0	1	-3	7	-17	58

Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores $v_1$ y $v_2$ del problema, que son $(754,1,0)$ y $(221,0,1)$ . Para la tercer columna, nos preguntamos ¿cuántas veces cabe $221$ en $754$ ? La respuesta es $3$ , así que ponemos un $3$ arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.

Para la cuarta columna, nos preguntamos ¿cuántas veces cabe $91$ en $221$ ? La respuesta es $2$ , así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un $0$ . La columna anterior nos dice que $13$ es el máximo común divisor, y que la combinación lineal es

$13=754\cdot 5 + 221 \cdot 58$

$\square$

Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.

Problema. Muestra que para todo entero $n$ se tiene que la fracción $\frac{41-6n}{9n-61}$ es irreducible para todo entero.

Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que $41-6n$ y $9n-61$ nunca tienen divisores en común.

Solución. Notemos que $41-6n$ y $9n-61$ tienen una combinación lineal que da $1$ . En efecto,

$3\cdot (41-6n) + 2\cdot (9n-61) = 123-18n+18n-122=1.$

Cualquier entero $d$ que divida a $41-6n$ y a $9n-61$ tiene entonces que dividir a $1$ , lo cual muestra que $\MCD{41-6n,9n-61}=1$ , y por lo tanto la fracción siempre es irreducible.

$\square$

Problema. Se tiene un número irracional $\alpha$ para el cual $\alpha^{91}$ y $\alpha^{119}$ son números racionales. Muestra que $\alpha^{14}$ es un número racional.

Sugerencia pre-solución. Encuentra el máximo común divisor de $91$ y $119$ . Recuerda que las potencias de racionales son racionales, y productos de racionales también.

Solución. Como $91=7\cdot 13$ y $119=7\cdot 13$ , tenemos que $\MCD{91,119}=7$ . De esta forma, existen enteros $m$ y $n$ tales que $7=91m+119n$ , de donde $14=91 \cdot (2m)+119 \cdot(2n)$ .

Sabemos que $\alpha^{91}$ es racional, así que $(\alpha^{91})^{2m}$ también. Análogamente, $(\alpha^{119})^{2n}$ es racional. De esta forma, el número

$\alpha^{14}=(\alpha^{91})^{2m}\cdot (\alpha^{119})^{2n}$

también lo es.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.1 del libro Problem Solving through Problems de Loren Larson.

El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo $n$ .

4 comentarios en “Seminario de Resolución de Problemas: Máximo común divisor”

Brashan Chinaski marzo 26, 2020 a las 7:05 pm

Hola, tenog un problema que no puedo resolver por métodos “faciles”

Si (a,b)=1 entonces (a al cuadrado, b al cuadrado)=1.
Supongo que es un buen problema usando sólo divisibilidad, ¿Puedes ayudarme?.

P.D: Ya lo demostre usando el teorema fundamental de la aritmetica, necesito tú ayuda.
Gracias

Responder ↓
1. Leo Autormarzo 26, 2020 a las 7:29 pm
  
  Es una buena pregunta. Aquí va una demostración que acabo de pensar. Supon que k es un entero que divide a a^2 y a b^2. Como a y b son primos relativos, hay una combinación lineal de ellos que da 1, digamos am+bn=1. Multiplicando esta igualdad por ab, tenemos a^2bm+ab^2n=ab. Como k divide a a^2 y b^2, entonces divide a ab. Ahora, regresa a la combinación lineal que da 1 y multiplica por a. Entonces a^2m+abn = a. Como k divide a a^2 y a ab, entonces divide a a. Análogamente divide a b. Pero a y b son primos relativos, así que k=1.
  
  Responder ↓
  1. Brashan Chinaski marzo 26, 2020 a las 10:59 pm
    
    Ohhh, esto estaba buscando, perdón por tardar en responder pero estaba ocupado resolviendolo pero no llegue a nada. Muchas gracias, aunque estoy preocupado, si podemos expresar números como combinación lineal i.e. ax+by=1 implica que serán coprimos? En caso de no ser así, existe una condición para poder determinar que tales x e y son únicos?
  2. Leo Autormarzo 27, 2020 a las 9:17 am
    
    Sí. Existe una combinación lineal entera ax+by=1 si y sólo si a y b son primos relativos (coprimos). Esos x y y nunca son únicos. Hoy publico una entrada de ecuaciones diofantinas en donde hablo de cómo son todas las posibles soluciones. Pero a grandes rasgos, si x y y hacen esta combinación lineal, también x-kb, y+ka son soluciones para cualquier entero k (y estas son todas las soluciones que existen).

Deja una respuesta Cancelar la respuesta

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Seminario de Resolución de Problemas: Máximo común divisor

Divisibilidad y máximo común divisor

Algoritmo de la división y algoritmo de Euclides

Más ejemplos

4 comentarios en “Seminario de Resolución de Problemas: Máximo común divisor”

Deja una respuesta Cancelar la respuesta

Divisibilidad y máximo común divisor

Algoritmo de la división y algoritmo de Euclides

Más ejemplos

Comparte esto:

4 comentarios en “Seminario de Resolución de Problemas: Máximo común divisor”

Deja una respuesta Cancelar la respuesta