Introducción

La entrada anterior fue un poco técnica y habló acerca de ideales en los números enteros. Podemos apoyarnos de los ideales para construir otras nociones conocidas de la teoría de números enteros. En esta entrada hablaremos de una de ellas: la de máximo común divisor.

Quizás recuerdes la idea general del máximo común divisor a partir de lo que aprendiste en la educación básica. Por ejemplo, si tenemos a los números $14$ y $35$,y queremos encontrar su máximo común divisor, lo que se hacía es escribir los divisores de ambos:

• Divisores de $14$: $1,2,7,14$.
• Divisores de $35$: $1,5,7,35$.

Ya teniendo ambas listas, se elige número más grande que estén en ambas: el $7$.

Con lo que platicaremos en esta entrada vamos a recuperar esta misma noción, sin embargo lo haremos desde un punto de vista un poco más teórico, el cual nos permitirá entender más aspectos de divisibilidad de los máximos comunes divisores.

Definición de máximo común divisor

Recordemos, que en la entrada pasada vimos cómo encontrar al «ideal más pequeño» que tuviera a dos números $a$ y $b$ enteros dados.

Proposición. Si $a$ y $b$ son enteros, entonces:

• El conjunto $M=\{ra+sb:r,s\in \mathbb{Z}\}$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$.
• Si $I$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$, entonces $M\subseteq I$.

Como $M$ es el ideal más pequeño que tiene a $a$ y a $b$, le llamamos el ideal generado por $a$ y $b$, y lo escribimos como $\langle a,b\rangle$.

Además, en la entrada anterior también vimos que cualquier ideal de $\mathbb{Z}$ forzosamente es de la forma $k\mathbb{Z}$ para algún entero no negativo $k$, es decir, que consiste justo de los múltiplos de algún entero no negativo $k$. Esto nos permite plantear la siguiente definición.

Definición. Si $a$ y $b$ son enteros, definimos a su máximo común divisor como el entero no negativo $k$ tal que $$k\mathbb{Z}=\langle a,b\rangle.$$ A este número $k$ a veces se le denota por $\text{MCD}(a,b)$, o bien simplemente $(a,b)$.

Esta es una definición muy distinta de la que nos dan en la educación básica, sin embargo, pronto recuperaremos las propiedades familiares: veremos que en efecto es un divisor de $a$, es un divisor de $b$, y que de entre los divisores en común, es el más grande de ellos. Antes de pasar a las propiedades, veamos un ejemplo.

Ejemplo. Tomemos a los enteros $6$ y $14$. ¿Qué ideal $I$ generan? Es decir, ¿quién es $\langle 6,8\rangle$? Bueno, dicho ideal $I$ debe tener a $6$ y $14$, así que por cerradura de la resta tiene también a $14-6-8$, y similarmente debe tener a $8-6=2$. Pero recordemos que los ideales también son cerrados bajo producto por cualquier entero, así que al estar $2$ en $I$, debe pasar que todos los números pares están en $I$. Y en efecto, los números pares son un ideal de $\mathbb{Z}$ que tienen a $6$ y $14$. Con esto acabamos de demostrar que $\langle 6,14 \rangle = 2\mathbb{Z}$. De este modo, por definición, el máximo común divisor de $6$ y $14$ es igual a $2$.

$\triangle$

Propiedades del máximo común divisor

En esta sección veremos dos propiedades muy importantes del máximo común divisor. Por un lado, veremos que siempre se puede escribir «como combinación» de los números originales, en un sentido muy específico. Por otro lado, recuperaremos las «propiedades usuales» que queremos que se cumplan por lo que aprendimos en educación básica.

Proposición. Sean $a$ y $b$ números enteros. Entonces, existen enteros $r$ y $s$ tales que $$(a,b)=ra+sb.$$

Demostración. Por definición, $(a,b)$ es el entero tal que $\langle a,b \rangle =(a,b)\mathbb{Z}$, en particular, $(a,b)$ está en $\langle a,b\rangle$. Pero también ya sabemos que $$\langle a,b \rangle = \{ra+sb:r,s\in \mathbb{Z}\}.$$ Como $(a,b)$ está en $\langle a,b \rangle$, entonces se puede escribir de la forma de los elementos del conjunto de la derecha también, es decir, existen enteros $r$ y $s$ tales que $$(a,b)=ra+sb.$$

$\square$

Como estamos poniendo a $(a,b)$ de la forma $ra+sb$, en donde los coeficientes de $a$ y $b$ son los números enteros $r$ y $s$, decimos que $(a,b)$ se puede escribir como una combinación lineal entera de $a$ y $b$. La proposición anterior nos demuestra la existencia de dicha combinación lineal, sin embargo no nos dice exactamente cómo encontrarla. Más adelante veremos el algoritmo de Euclides, el cual nos da una forma práctica de encontrar al máximo común divisor de dos números como combinación lineal de ellos.

Veamos ahora el resultado que nos dice que, en efecto, el máximo común divisor divide a cada número, y que es «el más grande» que hace esto.

Proposición. Sean $a$ y $b$ números enteros. Entonces, se cumple lo siguiente:

• $(a,b)|a$ y $(a,b)|b$.
• Si $d$ es algún otro número tal que $d|a$ y $d|b$, entonces $d|(a,b)$.

Demostración. Notemos que $a\in \langle a, b\rangle$, y que por definición $\langle a,b \rangle = (a,b) \mathbb{Z}$. De este modo, $a$ es múltiplo de $(a,b)$. Análogamente, $b$ es múltiplo de $(a,b)$. Esto muestra el primer inciso.

Ahora supongamos que $d$ es otro número tal que $d|a$ y $d|b$. Por la proposición anterior, existen enteros $r$ y $s$ tales que $(a,b)=ra+sb$. Como $d|a$, entonces $d|ra$. Como $d|b$, entonces $d|sb$. Así, $d|ra+sb=(a,b)$, como queríamos.

$\square$

La proposición anterior sí dice que el máximo común divisor divide a ambos, sin embargo no es totalmente directo por qué es el «máximo» en tamaño. La segunda parte habla más bien de una divisibilidad. Pero esto se traduce rápidamente a una desigualdad con la ayuda de las propiedades de la divisibilidad. Observa que si $d$ es un número tal que $d|a$ y $d|b$, entonces $d|(a,b)$. Tenemos entonces que $|d|\leq |(a,b)|$. Pero $(a,b)$ siempre es no negativo por definición, así que $|d|\leq (a,b)$. En resumen, tenemos el siguiente resultado.

Corolario. Si $a$ y $b$ son enteros y $d$ es un entero tal que $d|a$ y $d|b$, entonces $|d|\leq (a,b)$.

Números primos relativos (de máximo común divisor igual a uno)

Una situación muy especial en la teoría de los números ocurre cuando el máximo común divisor de dos números es igual a $1$.

Definición. Decimos que dos números enteros $a$ y $b$ son primos relativos si su máximo común divisor es igual a $1$. En símbolos, son primos relativos si $(m,n)=1$.

Por lo que hemos discutido hasta ahora, algunas de las consecuencias de que dos números $a$ y $b$ sean primos relativos son las siguientes:

• Si $d$ es un número que divide a $a$ y a $b$, entonces $|d|\leq (a,b)=1$, es decir, $d=1$ o $d=-1$. De este modo, los únicos divisores que tienen en común son el $1$ y el $-1$.
• El ideal generado por $a$ y $b$ es $1\cdot \mathbb{Z} = \mathbb{Z}$, es decir, consiste de todos los enteros.
• Por esa misma razón, se tiene que $\{ra+sb: r,s \in \mathbb{Z}\}=\mathbb{Z}$, en otras palabras, cualquier entero es combinación lineal entera de $a$ y de $b$.
• En particular, el $1$ es combinación lineal entera de $a$ y de $b$, es decir, existen enteros $r,s$ tales que $ra+sb=1$.

Estas consecuencias son prácticamente inmediatas de la definición, y es recomendable que intentes deducirlas por tu cuenta.

Veamos algunas otras propiedades que relacionan a los números primos relativos, con divisibilidad de algunas expresiones.

Proposición. Sean $a,b,c$ números enteros . Si $a\mid bc$ y $(a,b) = 1$, entonces $a\mid c.$

Demostración. Como $a$ divide a $bc$, existe $x \in \mathbb{Z}$ tal que $ax = bc$. Como $a$ y $b$ son primos relativos, sabemos que existen enteros $r$ y $s$ tales que $1 = ra+sb$. Multipliquemos esta última igualdad por $c$. Tenemos entonces que:
$$ c = rac + sbc = rac+ sax = a (rc+sx).$$

De aquí obtenemos la divisibilidad $a\mid c$ que buscábamos.

$\square$

En la proposición anterior es crucial la hipótesis de que $a$ y $b$ sean primos relativos. Por ejemplo, $7|28=14\cdot 2$, pero no pasa que $7|2$. Es decir, usualmente si dividimos a un producto, no se cumple que dividamos a cualquiera de sus factores.

A continuación tenemos otro resultado con un estilo similar.

Proposición. Sean $a,b,c \in \mathbb{Z}.$ Si $a\mid c$, $b\mid c$ y $(a,b) =1,$ entonces $ab \mid c$.

Demostración. Ya que $a,b$ son primos relativos, existen $m,n \in \mathbb{Z}$ tales que $1=am + bn $. Multipliquemos dicha ecuación por $c$: $$c=cam + cbn.$$

Como $a\mid c$ y $b\mid c$, existen $q,r \in \mathbb{Z}$ tales que $aq = c$ y $br = c$. Sustituyendo esto en la ecuación anterior, obtenemos que: $$c=cam + cbn = bram + aqbn = ab(rm+qn).$$

Esta igualdad justo nos dice que $ab\mid c$, como queríamos.

$\square$

Intenta encontrar un contraejemplo cuando no se cumple la hipótesis de que $a$ y $b$ son números primos relativos.

Más adelante…

Dejaremos el estudio del máximo común divisor hasta aquí por el momento. En la siguiente entrada hablaremos de un concepto muy cercano: el de mínimo común múltiplo. Así como en el caso de esta entrada, introduciremos la noción a partir de un contexto de ideales, para luego ver ejemplos y algunas propiedades clave.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

1. Demuestra todas las consecuencias de ser primos relativos de la lista enunciada en la entrada.
2. Prueba que dos enteros consecutivos siempre son primos relativos. Usa esto para demostrar que siempre que se eligen $51$ números distintos entre $1$ y $100$, forzosamente debes tener dos de ellos que sean primos relativos.
3. Sea $m$ un entero positivo. Demuestra que $(a,b)=1$ si y sólo si $(a^m, b^m) =1.$
4. De acuerdo a la entrada, al tomar dos números $a$ y $b$ podemos encontrar enteros $r$ y $s$ tales que $(a,b)=ra+sb$. Demuestra que siempre sucede que $(r,s)=1$.
5. Encuentra el máximo común divisor de $91$ y $70$ e intenta escribirlo como combinación lineal entera de ellos.

Entradas relacionadas

• Ir a Álgebra Superior II
• Entrada anterior del curso: Ideales en los enteros
• Siguiente entrada del curso: Mínimo Común Múltiplo

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»