Máximo común divisor
Consideremos dos números enteros Si \(a\) y \(b\) distintos de cero, decimos que \(c\) es un divisor común de \(a\) y \(b\) si \(c|a\) y \(c|b\). Cuando existen, únicamente, como divisores comunes 1 y -1 de los números \(a\) y \(b\) , estos se llaman coprimos o números primos entre sí.
Un número entero \(d\) se llama máximo común divisor de los números \(a\) y \(b\), \(d=\textbf{mcd}(a,b)\), cuando:
- d es divisor común de los números \(a\) y \(b\) y
- \(c\) es divisor de \(a\) y \(b\), entonces \(c|d\).
Algoritmo de Euclides
El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (mcd). Se basa en el siguiente resultado:
Teorema:
Si \(a\) y \(b\) son números enteros, \[\textbf{mcd}(a,b)=\textbf{mcd}(b,r),\] donde \(r\) es el resto del algoritmo de la división para \(a\) y \(b\) (\(a=qb+r\)).
Utilizando este resultado calculamos el mcd(a,b) de dos enteros (ambos >0, suponemos a > b) definiendo qi y ri recursivamente mediante las ecuaciones:
a = bq1 + r1 (0<r1<b)
b = r1q2 + r2 (0<r2<r1)
r1 = r2q3 + r3 (0<r3<r2)
….
rk-3 = rk-2qk-1 + rk-1 (0<rk-1<rk-2)
rk-2 = rk-1qk (rk=0)
Del teorema anterior, se sigue que:
\[\textbf{mcd}(a,b)=\textbf{mcd}(b,r_1)=\textbf{mcd}(r_1,r_2)=\ldots=\textbf{mcd}(r_{k-2},r_{k-1})=r_{k-1}\]
Una curiosidad es que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.
Ejemplo: Calcular \(\textbf{mcd}(2800733^3,255255^3)\)
Teorema Bézout
Teorema: Si \(d=mcd(a,b)\), entonces
\[\exists x,y\in\mathbb{Z};\, ax+by=d.\]
En la próxima sesión veremos el algoritmo de Euclides como método para calcular el mcd().
Mínimo común múltiplo
Aunque no lo utilizaremos tanto como el mcd también podemos definir el menor múltiplo común de a un conjunto de enteros:
Un número entero \(m\) se llama mínimo común múltiplo de los números \(a\) y \(b\), que notaremos por \(m=mcm(a,b)\), cuando:
- \(a|m\) y \(b|m\); es decir,m es un múltiplo común de los números \(a\) y \(b\) y
- \(c\in\mathbb{Z}^+\) es un múltiplo de \(a\) y \(b\), entonces \(m\leq c\).
Teorema: Dados dos números enteros \(a\) y \(b\), entonces \[mcm(a,b)=\frac{|ab|}{mcd(a,b)}\]
Ejercicio: ¿Cuánto suman las cifras del antepenúltimo resto obtenido mediante el algoritmo de la división de \(7171\) entre \(1771\)? |