Cálculo del máximo común divisor de dos números naturales

ENUNCIADO. Hallar el máximo común divisor de $15$ y $18$ empleando el algoritmo de Euclides ( también llamado de las divisiones sucesivas ) o, si se prefiere, empleando éste otro: el de las restas sucesivas.

SOLUCIÓN.

Cálculo del máximo común divisor de dos números naturales, empleando las restas sucesivas

ENUNCIADO. Hallar el máximo común divisor de $24$ y $18$, empleando el método de las restas sucesivas.

SOLUCIÓN. Teniendo en cuenta que, dados dos números naturales $a$ y $b$, tales que $a \ge b$, entonces $\text{m.c.d.}(a,b)=a$ si $a=b$ y en caso contrario $\text{m.c.d.}(a,b)=\text{m.c.d}(\text{máx}\{a-b,b\},\text{mín}\{a-b,b\})$. Por consiguiente, podemos aplicar una y otra vez dicha propiedad hasta obtener una diferencia igual a $0$, en cuyo caso el proceso finaliza, concluyendo que el máximo común divisor es igual al actual minuendo ( que es igual al sustraendo ). Y organizando los cálculos en una tabla, encontramos:

minuendo    sustraendo    diferencia
--------    ----------    ----------
24             18            6
18              6           12
12              6            6
6               6            0 (fin)

Así, pues, obtenemos $$\text{m.c.d.}(24,18)=6$$
$\square$

Ejercicio de aplicación del método de los factores para calcular el máximo común divisor y el mínimo común múltiplo

ENUNCIADO. Descomponer en factores primos los números $180$, $30$ y $120$. A continuación, emplear las reglas \emph{de los factores} para calcular el máximo común divisor y el mínimo común múltiplo de estos tres números.

SOLUCIÓN.
$\text{m.c.d}(180,30,120)=\text{m.c.d}(2^2\cdot 3^2\cdot 5\,,\,2\cdot 3\cdot 5\,,\,2^3\cdot 3 \cdot 5)=2\cdot 3 \cdot 5 =30$

$\text{m.c.m}(180,30,120)=\text{m.c.m}(2^2\cdot 3^2\cdot 5\,,\,2\cdot 3\cdot 5\,,\,2^3\cdot 3 \cdot 5)=2^3 \cdot 3^2\cdot 5=360$

$\square$

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$

Embalando libros para hacer un traslado

ENUNCIADO. Tenemos $14$ libros de química, $21$ libros de física y $35$ libros de matemáticas. Como queremos hacer un traslado, necesitamos ponerlos en cajas, de manera que en cada caja haya el mismo tipo libros y, también, el mismo número de libros. Si el número de cajas tiene que ser el menor posible, ¿ cuántos libros deberemos poner en cada caja ?. ¿ Cuántas cajas necesitaremos ?.

SOLUCIÓN.
Como ha de haber el mismo número de libros en cada caja, el número de libros que contenga cada una ha de ser un múltiplo común de $14$, $21$ y $35$. Además, al requerir que el número de cajas sea el menor posible, el número de libros en cada caja ha de ser el mayor posible. Así, pues, el número de libros por caja tiene que ser igual al mayor divisor común, esto es, al máximo común divisor de $14$, $21$ y $35$. Es claro que $\text{m.c.d.}(14,21,35)=\text{m.c.d}(7\cdot 2,7\cdot 3, 7\cdot 5)=7$, luego cada caja ha de contener $7$ libros.

El número de cajas necesarias para embalar los libros de química es, pues, igual a $14\div 7=2$. Para embalar los libros de física hacen falta $21 \div 7=3$ cajas. Y para embalar los libros de matemáticas necesitamos $35 \div 7=5$ cajas. Así que necesitamos un total de $2+3+5=10$ cajas para embalar todos los libros.
$\square$

Algunas propiedades útiles para el cálculo del mínimo común múltiplo y del máximo común divisor

P1.    $\text{m.c.m.}(a,b,c)=\text{m.c.m.}\left(\text{m.c.m.}(a,b),c\right)=\text{m.c.m.}\left(\text{m.c.m.}(a,c),b\right)=$
            $=\text{m.c.m.}\left(\text{m.c.m.}(b,c),a\right)$

      Ejemplo: Sea $a:=6$, $b:=15$, $c:=30$. Entonces, $\text{m.c.m.}(6,15,30)=\text{m.c.m.}\left(\text{m.c.m.}(6,15),30\right)=30$
            $=\text{m.c.m.}\left(\text{m.c.m.}(6,30),15\right)=\text{m.c.m.}(30,15)=30$
            $=\text{m.c.m.}\left(\text{m.c.m.}(15,30),6\right)=\text{m.c.m.}(30,6)=30$

P2.    $\text{m.c.d.}(a,b,c)=\text{m.c.d.}\left(\text{m.c.d.}(a,b),c\right)=\text{m.c.d.}\left(\text{m.c.d.}(a,c),b\right)=$
            $=\text{m.c.d.}\left(\text{m.c.d.}(b,c),a\right)$

      Ejemplo: Sea $a:=6$, $b:=15$, $c:=30$. Entonces, $\text{m.c.d.}(6,15,30)=\text{m.c.d.}\left(\text{m.c.d.}(6,15),30\right)=3$
            $=\text{m.c.d.}\left(\text{m.c.d.}(6,30),15\right)=\text{m.c.d.}(6,15)=3$
            $=\text{m.c.d.}\left(\text{m.c.d.}(15,30),6\right)=\text{m.c.d.}(15,6)=3$


P3.    $a\cdot b=\text{m.c.d.}(a,b)\cdot\text{m.c.m.}(a,b)$

      Ejemplo: Sea $a:=6$, $b:=15$. Entonces, $\text{m.c.d.}(6,15)=3$, $\text{m.c.m.}(6,15)=30$, y $a\cdot b=6\cdot 15=90$; y se cumple que $$6\cdot 15 = 30\cdot 3=90$$

OBSERVACIÓN. Esta tercera propiedad es muy útil, pues permite emplear los métodos de las restas sucesivas y el de las divisiones sucesivas ( algoritmo de Euclides ) para calcular, primero, el máximo común divisor de los dos números; y, a partir de éste, calcular el mínimo común múltiplo, pues es claro que deberá cumplirse que $$\text{m.c.m.}(a,b)=(a \cdot b) \div \text{m.c.d.}(a,b)$$

Recordemos que dos programa recursivos ( escritos en lenguaje LOGO ), bien sencillos, para calcular el máximo común divisor de dos números naturales son

procediment mcd_restes_successives :a :b
  si :a=:b 
     [escriu.seguit [mcd=] escriu :a  acaba] 
     [
       si :a<:b 
         [posa.a "b :a] 
       [posa.a "a (:a - :b) mcd_restes_successives :a :b]
     ]
fi

procediment mcd_Euclides :a :b
  fes.local "r residu :a :b
  si :r=0 
       [escriu.seguit [mcd=] escriu :b  acaba] 
     [
       posa.a "a :b
       posa.a "b :r
       mcd_Euclides :a :b
     ]
fi

Con ayuda de un intérprete de LOGO, escribimos
%mcd_restes_successives 3742036 1500872
o bien
%mcd_Euclides 3742036 1500872
y obtenemos
$$\text{m.c.d}(3742036,1500872)=4$$

Por consiguiente, y empleando la propiedad P3., $$\text{m.c.m.}(3742036,1500872)=(3742036 \cdot 1500872) \div \text{m.c.d.}(3742036,1500872)$$ y por tanto $$\text{m.c.m.}(3742036,1500872)=(3742036 \cdot 1500872) \div 4=1404079263848$$
$\square$

Aplicando la noción de máximo común divisor

ENUNCIADO. Dos listones de madera tienen longitudes respectivas de $32$ y $24$ decímetros. ¿ Cuántos trozos de igual longitud debemos cortar de uno y otro para que el número de dichos trozos sea el menor posible y de tal forma que no sobre ningún pedazo de listón ? ¿ Cuál será la longitud de cada uno de dichos trozos ?.

SOLUCIÓN.
La longitud $\ell$ de los trozos ha de ser un divisor común de las longitudes de uno y otro listón; además, si el número de trozos en que cortemos los dos listones ha de ser el menor posible, dicho divisor común ha de ser máximo, luego la longitud de los trozos es igual al máximo común divisor de $32$ y $24$. Para calcularlo, emplearemos el método de las restas sucesivas

con lo cual $$\text{m.c.d.}(32,24)=8$$ así que $\ell=8\,\text{dm}$. Por tanto, el número de trozos que obtendremos es $$(32+24)\div 8 = 7\; \text{trozos}$$
$\square$

Hallar el máximo común divisor de dos números naturales

ENUNCIADO. Hallar el máximo común divisor de $12$ y $15$

SOLUCIÓN.
Procedimiento 1. $\text{div}(12)=\{1,2,3,4,6,12\}$ y $\text{div}(12)=\{1,2,5,15\}$, luego $\text{divisores comunes}(12,15)=\{1,3\}$; así que, $$\text{m.c.d}(12,15)=\text{máximo}\{1,3\}=3$$

Procedimiento 2. Descomponiendo en producto de factores primos, $$12=2^2\cdot 3$$ y $$15=3\cdot 5$$ entonces, seleccionando los factores comunes con menor exponente, encontramos $$\text{m.c.d.}(15,12)=\text{m.c.d.}(2^2\cdot 3,3\cdot 5)=3$$

Procedimiento 3. Restando de manera iterada el menor de los dos números del mayor que vamos obteniendo de dichas restas, hasta encontrar un resultado menor que el menor de los dos números, alcanzamos el máximo común divisor en un sólo paso
$$15-12=3 \rightarrow \text{m.c.d.}(15,12)=3$$

Procedimiento 4. Empleando el método de Euclides -- que se basa en aplicar de forma iterada la siguiente propiedad: el máximo común divisor de dos números naturales $a$ y $b$ ( donde $a \ge b$ ) es igual al $b$ si $a$ es múltiplo de $b$ ( el resto de $a \div b$ es cero ), y si no $a$ no es múltiplo de $b$, el máximo común divisor de $a$ y $b$ es igual al máximo común divisor de $b$ y del resto de $a \div b$ --, vemos que el resto de la división $15\div 12$ es $3$; como dicho resto no es $0$, procedemos a dividir $12 \div 3$, y obtenemos resto igual a $0$, luego $\text{m.c.d.}(15,12)=3$
$\square$

Hallar el máximo común divisor de los siguientes números naturales ...

ENUNCIADO. Hallar el máximo común divisor de $12$, $18$ y $15$

SOLUCIÓN.
$\text{m.c.d}(12,18,15)$
  $=\text{m.c.d}(\text{m.c.d}(12,18),15)$
    $=\text{m.c.d}(\text{m.c.d}(2^2\cdot 3,2\cdot 3^2),15)$
      $=\text{m.c.d}(6,15)$
        $=\text{m.c.d}(2\cdot 3,3\cdot 5)$
          $=3$

$\square$

Cálculo del máximo común divisor por el método de los factores

ENUNCIADO. Calcúlese el máximo común divisor del conjunto de números naturales formado por $18$ y $15$

SOLUCIÓN. Hemos aprendido a encontrar el máximo común divisor de un conjunto de números: escribiendo las respectivas listas de divisores de los números de dicho conjunto; para, a partir de éstas, escribir la lista de los divisores comunes; y, finalmente, seleccionar el mayor número de dicha lista de divisores comunes. Éste es un método sencillo, pero poco práctico, pues si los números del conjunto dado no son pequeños, hacer todo eso es algo largo y tedioso. Veremos enseguida otro método más eficaz, al que llamamos método de los factores.

Empezaremos razonando a partir de la descomposición en factores primos de los números del conjunto dado. Observemos que $18=2\cdot 3^2$ y $15=3\cdot 5$. Como buscamos divisores comunes, podemos pensar en multiplicar todos los factores de la descomposición de sendos números siempre que dichos factores estén presentes en una y otra factorización; así, sólo podemos contar con '$3^2$ y '$3$', pues tanto el factor '$5$' como el factor '$2$' no son comunes a la expresión en factores de $18$ y de $15$. ¿ Con cuál nos quedamos ? ¿ Con '$3^2$' o bien con '$3$' ?. Como estamos buscando divisores comunes, no podemos seleccionar '$3^2$' como respuesta sino '$3$', así concluimos que $$\text{m.c.d}(18,15)=3$$

Intentemos extraer ahora algún patrón de lo que acabamos de hacer, que sea válido para los casos en que haya un número cualesquiera de números naturales en el conjunto dado, sea cual sea la descomposición en factores de todos los números de dicho conjunto.

  A partir de la descomposición en factores de cada uno de los números haremos lo siguiente:
    1. Seleccionaremos las bases [números primos] ( de la factorización de todos y cada uno de los números ) que sean comunes a todas y cada una de las factorizaciones
    2. El exponente de esas potencias que deberemos seleccionar ( de acuerdo a lo que hemos razonado en este problema ) será el menor de ellos
    3. Multiplicando las potencias así obtenidas, obtendremos el máximo común divisor.

Veamos un ejemplo: ¿ Cuál es el máximo común divisor del conjunto de números naturales $\{72,540,120\}$ ?
Paso 1. $72=2^3\cdot 3^2$, $540=2^2\cdot 3^3 \cdot 5 $ y $120=2^3\cdot 3 \cdot 5$. Como bases ( números primos ) de las potencias que son comunes a las tres factorizaciones, encontramos las bases $2$ y $3$
Paso 2. Ahora, de las factorizaciones, debemos tomar los menores exponentes de $2^{\square}$ y $3^{\square}$, esto es, $2^2$ y $3^2$
Paso 3. Finalmente, concluimos que $\text{m.c.d.}(72,540,120)=2^2\cdot 3^2=36$

$\square$

Divisores comunes de dos números naturales. Máximo común divisor.

[Para ver la imagen a mayor tamaño, haz clic sobre la misma]

Queremos embaldosar el suelo de una habitación rectangular ...

ENUNCIADO:
Queremos embaldosar el suelo de una habitación rectangular, de $24$ decímetros por $36$ decímetros, con baldosas cuadradas. ¿ Qué longitud debe tener el lado de dichas baldosas si deseamos que no quede ningún resquicio y que el número de las mismas sea el menor posible ? ¿ Cuántas baldosas necesitamos ?.

SOLUCIÓN:
El lado de cada baldosa ha de ser el mayor divisor común de las longitudes de sendos lados del suelo de la habitación, esto es, al máximo común divisor de $36$ y $24$, que es $12$. Las baldosas cuadradas deben medir, por tanto, $12$ dm de lado. Y el número de las mismas que se precisa es igual al número de veces que el lado de una baldosa está contenido a lo largo de uno de los lados del suelo de la habitación por el número de las mismas que el otro lado contiene; es decir, $\dfrac{36}{12} \cdot \dfrac{24}{12}= 3 \cdot 2 = 6$ baldosas. $\square$

Determinar el máximo común divisor de ...

Enunciat:
Determineu el màxim comú divisor de $12$ i $-14$

Solució:
A partir de la factorització de $12$, que és igual a $2^2\cdot 3$, trobem els divisors de $12$ són els següents nombres enters:
    $\{\pm 1,\pm 2,\pm 3, \pm 4, \pm 6, \pm 12\}$
conjunt de nombres que podem posar ordenats en la següent llista
    $\text{div}(12)=\{ -1,-2,-3,-4,-6,-12,1,2,3,4,6,12\}$

A partir de la factorització de $-14$, que és igual a $(-2)\cdot 7=2\cdot (-7)$, trobem els divisors de $-14$ són els següents nombres enters:
    $\{\pm 1,\pm 2, \pm 7,\pm 14\}$
conjunt de nombres que podem posar ordenats en la següent llista
    $\text{div}(-14)=\{ -1,-2,-7,1,2,7,14\}$

Els divisors comuns de $12$ i $-14$ són
    $\{ -2,-1,1,2\}$
i el màxim d'aquest conjunt és
    $\text{m.c.d}(12,-14)=\text{màxim}\big(\{ -2,-1,1,2\}\big)=\pm 2$

$\square$

Calcular el máximo común divisor y el mínimo común múltiplo de los siguientes números enteros

Enunciat:
    Traballant amb nombres enters, calculeu:
      a) el mínim comú múltiple de $-2$ i $8$
      b) el màxim comú divisor de $-2$ i $8$

Solució:
  a)
    Tinguem en compte que, ara, estem treballant amb nombres enters. Les idees sobre els conceptes de múltiples i divisors s'hi estenen a partir dels nombres naturals. En aquest cas, però, que volem trobar el mínim comú múltiple de dos nombres enters un dels quals és negatiu, cal donar, com a resultat en tots dos casos, el múltiple comú més proper (als nombres enters donats). El múltiples de $-2$ y $8$ son, respectivament:
      $\dot{(-2)}=\dot{(2)}=\{\ldots,-10-8,-6,-4,-2,0,2,4,6,8\ldots\}$
      $\dot{(-8)}=\dot{(8)}=\{\ldots,-16,-8,0,8,16,\ldots\}$
d'on trobem que
      $\text{m.c.m}(-2,8)=\pm 8$

Observació 1: Si féssim servir l'algorisme dels factors, treballant amb nombres enters ( no només amb nombres naturals ), d'aquí cal entendre, per tant, que $$\text{m.c.m}(2,-8)=\text{m.c.m}(\left|-2\right|,8)=\pm 8$$
$\square$

  b)
    Per calcular el màxim comú divisor de $-2$ i $8$ ( que és el mateix que el de $8$ i $-2$ ) podem fer ús del mètode de les llistes (de divisors), és a dir, trobar tots els divisors de cada un dels dos nombres; i, a partir d'aquestes llistes, escriure la dels divisors comuns; i, finalment, mirar quin és el més gran (ara, en valor absolut). O bé, havent calculat ja el mínim comú múltiple, podem també fer ús de següent propietat ( que ja hem fet servir altres vegades ):
        $\text{m.c.m}(a,b) \times \text{m.c.d}(a,b)=a \cdot b$
així,
        $\pm 8 \times \text{m.c.d}(-2, 8)=-2 \cdot 8$
és a dir
        $\pm 8 \times \text{m.c.d}(-2, 8)=-16$
per tant
        $\text{m.c.d}(-2, 8)=-16 \div (\pm 8)=\pm 2$

Observació 2: Si féssim servir l'algorisme dels factors, treballant amb nombres enters ( no només amb nombres naturals ), d'aquí cal entendre, per tant, que $$\text{m.c.d}(-2,8)=\text{m.c.d}(\left|-2\right|,8)=\pm 2$$
$\square$

máximo común divisor y mínimo común múltiplo de un conjunto de números enteros

Enunciado:
  Calcular el mínimo común múltiplo y el máximo común divisor de los siguientes números enteros: $12$, $-4$ i $18$.

Ayuda:
Utilizar las siguientes propiedades:
1.         $\text{m.c.m}(a,b,c)=\text{m.c.m}\big(\text{m.c.m}(a,b),c\big)$
                                $=\text{m.c.m}\big(a,\text{m.c.m}(b,c)\big)$

2.         $\text{m.c.d}(a,b,c)=\text{m.c.d}\big(\text{m.c.d}(a,b),c\big)$
                                $=\text{m.c.d}\big(a,\text{m.c.d}(b,c)\big)$

Solución:
        $\text{m.c.m}(12,-4,18)=\text{m.c.m}\big(\text{m.c.m}(12,\left|-4\right|),18\big)$
                                $=\text{m.c.m}(12,18)$
                                $=\pm 36$

        $\text{m.c.d}(12,-4,18)=\text{m.c.d}\big(\text{m.c.d}(12,\left|-4\right|),18\big)$
                                $=\text{m.c.d}(4,18)$
                                $=\pm 2$

Determinar el máximo común divisor y el mínimo común múltiplo ...

Enunciado:
    Calcular:
      a) el máximo común divisor de $-2$ i $-8$
      b) el mínimo común múltiplo de $-2$ i $8$

Solución:
  a)
Teniendo en cuenta que los divisores de sendos números son:
      $\text{div}(-2)=\{-2,-1,-1,2\}$
      $\text{div}(-8)=\{-8,-4,-2,-1,1,2,4,8\}$
vemos que
            $\text{m.c.d}(-2,-8)=\pm 2$

  b)
Y, por la siguiente propiedad,
        $\text{m.c.m}(a,b) \times \text{m.c.d}(a,b)=a \cdot b$
obtenemos
        $\text{m.c.m}(-2,-8) = \big((-2)\cdot (-8)\big) \div \text{m.c.d}(-2,-8)$
                                        $= \big((-2)\cdot (-8)\big) \div (\pm 2)$
                                        $= 16 \div (\pm 2)$
                                        $= \pm 8$
$\square$