Cálculo del M.C.D. mediante el algoritmo de Euclides
Resumen inicial
El algoritmo de Euclides halla el M.C.D. mediante divisiones sucesivas: $\operatorname{MCD}(a, b) = \operatorname{MCD}(b, r)$ hasta obtener residuo 0.
Explicación en palabras simples
El algoritmo de Euclides es un método eficiente para encontrar el M.C.D. de números grandes. Dividimos el número mayor entre el menor; si el residuo no es cero, dividimos el divisor anterior entre este nuevo residuo, y repetimos el proceso hasta que el residuo sea cero. El último residuo distinto de cero es el M.C.D.
Explicación formal
Dado el par $a, b \in \mathbb{N}$ con $a > b$, el Algoritmo de Divisiones Sucesivas de Euclides genera la secuencia de residuos $r_1, r_2, \dots, r_k$:
$$a = b \cdot q_1 + r_1, \quad b = r_1 \cdot q_2 + r_2, \quad \dots, \quad r_{k-2} = r_{k-1} \cdot q_k + r_k$$
$$\text{Si } r_k = 0 \implies \operatorname{MCD}(a, b) = r_{k-1}$$
Desglose de la fórmula:
- Identidad fundamental: $\operatorname{MCD}(a, b) = \operatorname{MCD}(b, r_1) = \operatorname{MCD}(r_1, r_2) = \dots = r_{k-1}$.
- Condición de término: El algoritmo finaliza al obtener un residuo nulo $r_k = 0$.
Complemento didáctico: El M.C.D. es el último resto no nulo del proceso, lo que permite trabajar con números gigantes sin necesidad de factorizar.
La alternativa correcta es 'El último resto distinto de cero antes de obtener el residuo nulo'.
Definiciones clave
- Algoritmo de Euclides: Procedimiento de reducción por residuos sucesivos para obtener el M.C.D.
- Último resto no nulo: El valor $r_{k-1}$ que constituye el M.C.D. final.
Ejemplo guiado
Calcule el $\operatorname{MCD}(105, 45)$ utilizando el algoritmo de división euclidiana.
- Paso 1: Dividir 105 entre 45: $105 = 45 \cdot 2 + 15$ (residuo $r_1 = 15 \neq 0$).
- Paso 2: Dividir 45 entre el residuo 15: $45 = 15 \cdot 3 + 0$ (residuo $r_2 = 0$).
- Paso 3: Identificar el último resto distinto de cero: el residuo anterior fue $15$.
- Conclusión: $\operatorname{MCD}(105, 45) = 15$.
La alternativa correcta es '15'.
Procedimiento
- Paso 1: Dividir el número mayor entre el número menor obteniendo el resto $r_1$.
- Paso 2: Si $r_1 \neq 0$, dividir el divisor anterior entre $r_1$ obteniendo $r_2$.
- Paso 3: Repetir las divisiones de divisor por resto hasta obtener un resto igual a 0.
- Paso 4: Declarar como M.C.D. el último resto no nulo obtenido.
Errores frecuentes y cómo corregirlos
-
Error 1: Confundir el M.C.D. con el cociente final en lugar del residuo. Cómo corregirlo: El M.C.D. es el ÚLTIMO RESTO no nulo, NO el cociente de la división.
-
Error 2: Invertir el orden dividiendo el menor por el mayor. Cómo corregirlo: En la primera división se divide el número mayor entre el menor.
Ejemplos
Responde los siguientes ejercicios para poner a prueba lo que acabas de aprender.
- $252 = 105 \cdot 2 + 42$. $105 = 42 \cdot 2 + 21$. $42 = 21 \cdot 2 + 0$. Último resto no nulo: 21.
- Evita tener que factorizar números grandes en factores primos.
- Sí, es la propiedad que sostiene matemáticamente el algoritmo.
- No, el M.C.D. es el resto ANTERIOR al resto cero.
Ejemplos Verdadero/Falso
Decide si cada afirmación es verdadera o falsa antes de ver la explicación.
Esta afirmación describe un error frecuente: es incorrecta.
Esta afirmación describe un error frecuente: es incorrecta.
Esta afirmación describe un error frecuente: es incorrecta.
Esta afirmación es correcta.
Esta afirmación describe un error frecuente: es incorrecta.
Esta afirmación describe un error frecuente: es incorrecta.
Esta afirmación es correcta.
Al terminar debes poder
Calcular el máximo común divisor de números de varias cifras aplicando el algoritmo de divisiones sucesivas de Euclides.
Aplicando reiteradamente la relación del algoritmo de la división $a = b \cdot q + r \implies ext{mcd}(a, b) = ext{mcd}(b, r)$ hasta obtener residuo $r = 0$, reconociendo al último resto no nulo como el MCD.
Practica
Preguntas conceptuales
Verificar las ideas clave antes de calcular.
-
Si al dividir un número $a$ por un número $b$ la división es exacta (resto = 0), ¿cuál es el Máximo Común Divisor de ambos números?
Si el resto es 0, entonces $b$ divide exactamente a $a$. El mayor divisor común posible entre $a$ y $b$ es entonces el propio $b$.
Respuesta: $b$
-
¿En qué propiedad matemática de la división entera se basa el Algoritmo de Euclides para calcular el MCD de dos números $a$ y $b$ (con $a > b$)?
El Algoritmo de Euclides se basa en la propiedad de que los divisores comunes de $a$ y $b$ son los mismos que los de $b$ y el resto $r$ de dividir $a$ por $b$.
Respuesta: $\text{MCD}(a, b) = \text{MCD}(b, r)$, donde $r$ es el resto de la división de $a$ entre $b$.
-
En el Algoritmo de Euclides por divisiones sucesivas, ¿cómo sabemos que hemos llegado al final del proceso?
El algoritmo finaliza cuando el resto es 0, lo que indica que la última división fue exacta. El divisor de esta última división es el MCD.
Respuesta: Cuando obtenemos un resto igual a 0.
Reconocimiento
Identificar elementos, datos o procedimientos.
-
Si estamos aplicando el Algoritmo de Euclides para calcular el MCD de 105 y 40, realizamos la primera división: $105 = 40 \cdot 2 + 25$. ¿Cuál es la siguiente división que debemos plantear?
En el siguiente paso del algoritmo de Euclides, reemplazamos el dividendo por el divisor anterior (40) y el divisor por el resto anterior (25), por lo que dividimos 40 entre 25.
Respuesta: Dividir 40 por 25
Ejercicios básicos
Aplicar el procedimiento principal en casos simples.
-
¿Es verdadero que al aplicar el Algoritmo de Euclides para 90 y 30, el proceso termina en la primera división con resto 0, indicando que el MCD es 30?
$90 = 30 \cdot 3 + 0$. Como el resto es 0, el divisor 30 es el MCD.
Respuesta: Verdadero
-
¿Es verdadero que si aplicamos divisiones sucesivas a los números 45 y 18, obtenemos como restos sucesivos 9 y luego 0, por lo que el MCD es 9?
Paso 1: $45 = 18 \cdot 2 + 9$ (resto 9). Paso 2: $18 = 9 \cdot 2 + 0$ (resto 0). El último divisor es 9, que es el MCD.
Respuesta: Verdadero
-
¿Es verdadero que el primer resto al aplicar el Algoritmo de Euclides para 75 y 20 es 15?
$75 \div 20 = 3$ con resto $15$ ($20 \cdot 3 = 60$, y $75 - 60 = 15$). Por lo tanto, el resto es 15.
Respuesta: Verdadero
Preguntas tipo PAES
Resolver preguntas con formato y distractores similares a PAES.
-
Para un proyecto escolar se quieren armar kits de herramientas. Se tienen 525 lápices y 210 reglas. Aplicando el algoritmo de divisiones sucesivas para encontrar el número máximo de kits idénticos que se pueden formar con todas las herramientas, ¿cuál es dicho número?
Aplicamos Euclides a 525 y 210: $525 = 210 \cdot 2 + 105$; luego $210 = 105 \cdot 2 + 0$. Como el resto es 0, el MCD es 105.
Respuesta: 105
-
Se desea dividir un terreno rectangular de $252\text{ m}$ de largo y $180\text{ m}$ de ancho en parcelas cuadradas del mayor tamaño posible sin que sobre terreno. Si se calcula el MCD mediante el algoritmo de Euclides, ¿cuánto debe medir el lado de cada parcela cuadrada?
Calculamos el $\text{MCD}(252, 180)$ por divisiones sucesivas: $252 = 180 \cdot 1 + 72$; luego $180 = 72 \cdot 2 + 36$; luego $72 = 36 \cdot 2 + 0$. El último divisor no nulo es 36.
Respuesta: $36\text{ m}$
-
Un programador necesita calcular el MCD de dos números grandes, $A = 1230$ y $B = 450$, para optimizar una función de espaciamiento. Aplicando divisiones sucesivas (algoritmo de Euclides), ¿cuál es el resto de la primera división y cuál es el MCD final?
Primera división: $1230 = 450 \cdot 2 + 330$ (resto 330). Siguientes pasos: $450 = 330 \cdot 1 + 120$ (resto 120); $330 = 120 \cdot 2 + 90$ (resto 90); $120 = 90 \cdot 1 + 30$ (resto 30); $90 = 30 \cdot 3 + 0$ (resto 0). El MCD es 30.
Respuesta: El resto es 330 y el MCD es 30