Algoritmo de Euclides: MCD sin factorizar

¿Qué es?

• Es una receta para hallar el MCD de dos números sin factorizar.
• Solo haces divisiones seguidas y te quedas con los restos.
• Cuando llegas a resto 0, el último divisor es el MCD.

Palabras clave

• División con resto:

$$a = bq + r$$

donde $q$ es el cociente y $r$ es el resto.

• Resto: lo que sobra de la división. Siempre cumple $0 \le r < b$.
• Divisor: número que divide en forma exacta. Ejemplo: $3$ es divisor de $12$ porque $12 = 3 \cdot 4$.

Analogía: cortar una cinta sin desperdiciar

• Imagina dos cintas, una de $48$ cm y otra de $18$ cm.
• Quieres cortarlas en pedazos iguales, lo más largos posible, sin que sobre nada.
• Ese largo ideal es el $MCD(48,18)$.
• Euclides hace lo mismo: corta, usa el sobrante para medir de nuevo, hasta que ya no sobra nada.

La idea clave

• Regla de oro:

$$MCD(a,b) = MCD(b,r)$$

donde $r$ es el resto de dividir $a$ entre $b$.

• ¿Por qué funciona? Todo divisor común de $a$ y $b$ también divide al resto $r$, y al revés también.
• Entonces la pareja $(a,b)$ y la pareja $(b,r)$ tienen los mismos divisores comunes y el mismo MCD, pero con números más pequeños.

Pasos del algoritmo

Para $MCD(a,b)$ con $a > b$:

1. Divide $a$ entre $b$. Anota cociente $q$ y resto $r$.
2. Si $r = 0$, termina. El MCD es $b$.

Cadena del proceso:

$$a \to b \to r_1 \to r_2 \to \dots \to 0$$

Ejemplo resuelto: $MCD(1071,462)$

• Paso 1:

$$1071 = 462 \cdot 2 + 147$$

Resto $147 \neq 0$, seguimos con $(462,147)$.

• Paso 2:

$$462 = 147 \cdot 3 + 21$$

Resto $21 \neq 0$, seguimos con $(147,21)$.

• Paso 3:

$$147 = 21 \cdot 7 + 0$$

Resto $0$, paramos.

• Conclusión: el último divisor usado fue $21$, entonces $MCD(1071,462) = 21$.

Lo esencial para recordar

• Euclides halla el MCD solo con divisiones y restos.
• Usa $MCD(a,b) = MCD(b,r)$ para reemplazar los números por otros más pequeños.
• Repites: divide, mira el resto, y si no es $0$ continúas con $(b,r)$.