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:

  1. f(a,a)=a para todo entero positivo a.
  2. f(a,b)=f(b,a) para todo par de enteros positivos a y b.
  3. 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.

3223
7542219139130
101-25-17
01-37-1758

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

  1. Brashan Chinaski

    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. LeoLeo Autor

      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

        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. LeoLeo Autor

        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

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

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