jueves, 1 de diciembre de 2016

Empleando el algoritmo de Euclides para hallar el máximo común divisor de dos números enteros

ENUNCIADO. Hallar el máximo común divisor de $28$ y $21$, empleando el algoritmo de Euclides. A continuación, y a partir de dicho resultado, calcular el mínimo común múltiplo.

SOLUCIÓN.
Recordemos la siguiente propiedad:
Dados dos números enteros $a$ y $b$, siendo $a \ge b$; y considerando la división euclídea $a\div b$, donde $r$ es el resto de la misma, entonces $\text{m.c.d}(a,b)=b$ si $r=0$; y, si $r\neq 0$, entonces $\text{m.c.d}(a,b)=\text{m.c.d}(b,r)$.

El algoritmo de Euclides consiste pues en aplicar dicha propiedad, una y otra vez, realizando divisiones sucesivas, de tal modo que, en cada paso, el nuevo dividendo sea el antiguo divisor y el nuevo divisor el antiguo resto, hasta llegar a una división con resto igual a cero. Llegados a este punto, el máximo común divisor ha de ser igual al divisor en dicho paso, finalizando así el algoritmo.

Podemos organizar los cálculos de las divisiones sucesivas en una tabla. Así, para los números dados en este ejercicio, obtenemos
    dividendo        divisor      resto
   ----------        -------     ------
      28               21          7
      21                7          0
luego $$\text{m.c.d}(28,21)=7$$

Calculemos a continuación el mínimo común múltiplo de $28$ y $11$. Como ya conocemos el máximo común divisor, que es $7$, vamos a utilizar otra propiedad que también hemos estudiado:

Dados dos números enteros $a$ y $b$, entonces se cumple que $$\text{m.c.m}(a,b)\cdot \text{m.c.d.}(a,b)=a\cdot b$$ Para los números dados, tenemos pues que $$\text{m.c.m}(28,21) \cdot 7=28\cdot 21$$ por tanto $$\text{m.c.m.}(28,21)=28\cdot 21 \div 7 = 84$$

$\square$