Mcd

El máximo común divisor

Si $a,b \in \mathbb{Z}$ son enteros arbitrarios, entonces ex entero $d$ es un un divisor común de $a,b$ si divide tanto a $a$ como $b$. El conjunto de divisores comunes positivos es no vacío pues al menos 1 está ahí.

Si tanto $a=b=0$ entonces cualquier entero es un divisor común. Sin embargo, si al menos uno de ellos es diferente de cero, hay sólo una cantidad finita de divisores comunes positivos. Dentro de ellos hay uno que es el mayor.

Definición: Sean $a,b \in \mathbb{Z}$ tal que al menos uno de ellos es diferente de cero. El máximo común divisor de $a \land b$, denotado por mcd(a,b) o por (a,b) es el entero positivo $d$, tal que:

  • $d|a \land d|b$
  • Si $c|a \land c|b \rightarrow c\le d$.

El siguiente teorema muestra que el $mcd(a,b)$ se puede escribir como una combinación lineal de $a \land b$:

Teorema: Dados enteros $a,b$ con $ab\ne 0$, existen enteros $x,y$ tal que $mcd(a,b)=ax+by$.

Demostración: Sea $I=\left\{ ax+by : x,y\in \mathbb Z \land ax+by >0 \right\}$ este conjunto es no vacío pues al menos $| a | \lor | b |$ está en $I$. Por el principio del buen orden, este conjunto tiene un primero elemento. Llamemos a este elemento $d$. Afirmamos que $d=mcd(a,b)$. En efecto, por el algoritmo de la división existen enteros $q,r$ con $0\le r<d$ tal que $a= dq + r$ entonces como $d\in I$ existen enteros $x,y$ tal que $d=ax+by$ entonces

(1)
\begin{equation} r= a(1)+d(-q) = a(1)+(ax+by)(-q) = a(1-qx)+ b(-qy) \end{equation}

implicando que $r=0$ y por lo tanto $d|a$. De manera análoga demostramos que $d|b$ por lo que $d$ es un divisor común. Ahora demostremos que es el mayor de entre los divisores positivos. Sea entonces $m$ un divisor positivo común de $a\land b$, existen enteros $c,t$ tales que $a=mc \land b = mt$ y como $d=ax+by = mcx + mty = m(cx+ty)$ tenemos que $m|d$ por lo que $m\le d$ Q.E.D.

Con lo anterior además demostramos que todo divisor común de $a \land b$ es también un divisor de $d=mcd(a,b)$.

Corolario: Todo divisor común de $a,b$ es un divisor de $d=mcd(a,b)$ y viceversa, todo divisor de $d$ es un divisor común de $a\land b$.

Corolario: El conjunto $I = \left\{ ax+by: x,y\in \mathbb{Z} \right\}$ es precisamente el conjunto de múltiplos de $d$.

Demostración: Si $d|m$ entonces $dc=m$ para algún $c\in \mathbb{Z}$ y entonces $m=cd=c(ax+by)=a(cx)+ b(cy)$. Conversamente es claro que $d$ divide a cualquier combinación lineal de $a,b$ por ser un divisor común.

Puede suceder que los únicos divisores comunes de un par de números sean el $1,-1$. Este caso decimos que los enteros son primos relativos (o que son coprimos).

Definición: Dos enteros $a,b$ son primos relativos si $mcd(a,b)=1$.

Corolario: Dos enteros $a,b$ son primos relativos sí y sólo si, existen enteros $x,y$ tales que $1=ax+by$.

Los resultados nos dan un criterio útil reducir a números primos relativos.

Proposición: Si $(a,b)=d \rightarrow (a/d,b/d)$.

Demostración: Sabemos que existen enteros $x,y$ tal que $d=ax+by$ como $d$ es un divisor común podemos escribir $a=dc \land b=dq$ para algunos enteros $c,q$ por lo que $d= d(cx+qy)$ y entonces $1=cx+qy$ y por el corolario anterior $(a/d,d/b)=1$.

Ejemplo: $(-12,30) = 6$ entonces $(-12/6, 30/6) = (-2, 5) = 1$.

Corolario: Si $a|c \land b|c$ y si $(a,b)=1$ entonces $ab|c$.

Demostración: Existen enteros $x,y$ tal que $1=ax+by$, multiplicando por $c$ obtenemos $c=(ac)x+(bc)y$ y como $ab| ac$ pues $b|c \rightarrow ab|ac$ y como $ab| bc$ entonces $ab | (ac)x+(bc)y = c$.

Notar que la hipótesis de que $(a,b)=1$ no puede ser removida pues en general no es vedad que se $a|c \land b|c \rightarrow ab|c$ por ejemplo tomar $a=4, b=6$ entonces tanto $a,b | 12$ pero $ab \nmid 12$.

Teorema (Teorema de Euclides): Si $a|bc$ y $(a,b)=1$ entonces $a|c$.

Demostración: Existen enteros tal que $1=ax+by$ entonces al multiplicar por $c$ tenemos $c= (ac)x + (bc)y$ como por hipótesis $a|bc$ y como $a|acx$ claramente, entonces $a| (ac)x + (bc)y$ es decir $a|c$. Q.E.D.

Notemos que de igual manera, si la hipótesis $(a,b)=1$ es removida, entonces el resultado no sigue siendo cierto.

Ejercicio: Demuestra que $(ma,mb)=m(a,b)$. Esto nos permite calcular el máximo común divisor de dos números si conocemos algunos de sus divisores. Este nos proporciona el algoritmo de la primaria para encontrar el mcd.

El algorítmo de Euclides

Un algoritmo "eficiente" para calcular el máximo común divisor de dos enteros se puede conseguir aplicando repetidamente el algoritmo de Euclides. Este algoritmo fue dado por Euclides en su famoso libro de los Elementos, aunque hay evidencias de que el algoritmo es más antiguo que Euclides.

Primero observemos que $(| a |, | b |) = (a,b)$ por lo que basta asumir que $a,b\in \mathbb{Z}$ son positivos. Sin perdida de generalidad podemos asumir también que $a\ge b$.

Por el algoritmo de la división existe enteros $q,r$ con $0\le r < b$ tal que

(2)
\begin{equation} a=bq+r \end{equation}

Afirmación: $(a,b)=(b,r)$. En efecto si $m$ es un divisor común de $a \land b$ entonces $m|r$ pues este es una combinación lineal de $a \land b$, por lo que entonces $r$ es un divisor común de $b\land r$. Análogamente si $n\mid b \land m\mid r$ entonces $n\mid a$ por lo que $a\land b$ tiene exactamente el mismo conjunto de divisores comunes que $b,r$. Por lo tanto $(a,b)=(b,r)$.

Esto ya nos muestra una forma de calcular el máximo común divisor de dos números $a,b$ de una manera más sencilla pues en principio $b,r$ son números más pequeños.

El primer paso es aplicar el algoritmo para la división:

(3)
\begin{align} a=q_1b+r_1 \qquad 0\le r_1<b \end{align}

$r_1=0$ entonces $b\mid a$ y $(a,b)=b$. De lo contrario la observación anterior nos muestra que $(a,b)=(b,r_1)$ y entonces aplicamos el algoritmo de la división para $b, r_1$ para obtener:

(4)
\begin{align} b= r_1q_2+r_2 \qquad 0\le r_2\le r_1 \end{align}

Si $r_2 =0$ entonces $r_1\mid b$ y $(a,b)=(b,r_1)= r_1$ de lo contrario podemos aplicar el algoritmo de la división nuevamente. Como los números encontrados satisfacen $b> r_1> r_2 > r_3 \cdots >r_n \ge 0$ vemos que este proceso tiene que terminar (en a lo meas $b$ pasos), es decir para algún $n\le b$ debemos tener que $r_n=0$ y entonces:

(5)
\begin{align} (a,b)=(b,r_1)=(r_1,r_2) =\cdots= (r_{n-2},r_{n-1}) = (r_{n-1}, 0) = r_{n-1}. \end{align}

En otras palabras, el máximo común divisor de $a\land b$ es el último residuo distinto de cero al aplicar repetidamente el algoritmo de la división como en proceso anterior.

Ejemplo: Calculemos $(2024,748)$.

(6)
\begin{align} 2024=748(2)+ 528\\ 748=528(1)+220\\ 528=220(2)+88\\ 220=88(2)+44\\ 88=44(2)+0 \end{align}

Por lo tanto $(2024,748)=44$.

Nosotros sabemos que el máximo común divisor de dos números $(a,b) = ax+by$ para algunos enteros $x,y$. El algoritmo de Euclides también nos brinda una forma de encontrar los enteros $x,y$. En efecto, si $(a,b)= r_n$ entonces $r_{n-2} = r_{n-1}q_{n}r_{n-1}$ y entonces $r_n = {r_{n-2}} - q_nr_{n-1}$. Ahora resolvemos la ecuación anterior en el algoritmo para $r_{n-1}$ y lo substituimos para obtener:

(7)
\begin{equation} r_n = r_{n-2}-q_n(r_{n-3}-q_{n-1}r_{n-2}) = (1+q_nq_{n-1})r_{n-2} + (-q_n)r_{n-3}. \end{equation}

Esto representa a $r_n$ como una combinación lineal de $r_{n-2} \land r_{n-3}$. Si continuamos con este proceso regresando por las distintas ecuaciones, vamos eliminando sucesivamente los residuos hasta el último paso que llegaríamos a expresar $r_n$ como una combinación linear de $a\land b$.

Proposición: Si $k>0$ entonces $(ka,kb)=k(a,b)$.

Demostración: Podemos asumir que también $a\ge b >0$. Por el algoritmo de la división $a=bq+r$ con $0\le r< b$. Si multiplicamos esta igualdad por $k$ tenemos que $ak=(bk)q+(rk)$ con $0\le rk < bk$ es decir que $rk$ es el residuo de $ak$ al aplicar el algoritmo de la división con $bk$. Este análisis es el mismo en cada paso del algoritmo de Euclides, por lo que el último residuo distinto de cero en el algoritmo de Euclides aplicado a $ak,bk$ será k(a,b), es decir $(ak,bk)=k(a,b)$.

Corolario: Para cada entero $k\ne 0$ $(ka,kb)= | k |(a,b)$.

Definición: Un entero $c$ es un múltiplo común de $a,b$ si $a\mid c \land b\mid c$. Si $ab\ne 0$, el conjunto múltiplos comunes positivos es distinto del vacío y por lo tanto tiene un elemento mínimo. Este elemento es llamado el mínimo común múltiplo de $a \land b$. Este es denotado por $mcm(a,b)= [a,b]$.

Por ejemplo $[-12, 30]=60$.

Teorema: Para enteros positivos $a,b$ se tiene que:

(8)
\begin{equation} (a,b)[a,b] = ab \end{equation}

Demostración: Sea $d=(a,b)$ y $m=[a,b]$ entonces $ab/d \in \mathbb{Z}$ y es un múltiplo común de $a \land b$ por lo tanto
$m\le ab/d$ es decir $md\le ab$ por orto lado sabemos que $d=ax+by$ y que $m=as=br$ por lo que

(9)
\begin{equation} dm=(ax+by)m=amx+bmy = abxr+ abys = ab(xr+ys) \end{equation}

es decir $ab\mid dm$ y entonces $ab\le dm$ completando la prueba.

De la prueba anterior concluimos que:

Corolario El mínimo común múltiplo divide a cualquier múltiplo común. Es decir, si $a|c \land b|c$ entonces $[a,b]\mid c$.

En efecto, si $a\mid c \land b\mid c$ entonces $ab\mid cd =cax+cby$ pero $ab=dm$ por lo que $dm \mid dc$ y entonces $m\mid c$.

Corolario: Si $[a,b]=ab \Rightarrow (a,b)=1$.

Notemos que es posibles definir el máximo común divisor y el mínimo común múltiplo para cualquier número finito de enteros, por lo que también podemos definir el concepto de que un número de enteros sean primos relativos, pidiendo que su máximo común divisor sea uno. Notar sin embargo que esto no significa que los enteros sean primos relativos dos a dos.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License