Algoritmo de Euclides

El **algoritmo de Euclides** es una forma rápida de hallar el **máximo común divisor (MCD)** de dos números naturales sin hacer listas de divisores ni árboles de factores. Divide el número mayor $a$ entre el número menor $b$ y escribe el resultado como una **división con resto** (división entera): $$a = q \times b + r, \quad 0 \le r < b$$ Aquí $q$ es el **cociente** y $r$ es el **resto**. Después **sustituye la pareja $(a, b)$ por $(b, r)$** y vuelve a dividir. Repite hasta que el resto sea $0$. El **último resto distinto de cero** (el divisor de la última fila) es el MCD. **Ejemplo:** $\text{MCD}(48, 18)$ - $48 = 2 \times 18 + 12$ - $18 = 1 \times 12 + 6$ - $12 = 2 \times 6 + 0$ El resto es $0$, así que $\text{MCD}(48, 18) = 6$. **Por qué funciona:** si un número $d$ divide a la vez a $a$ y a $b$, también divide a $r = a - q \times b$. Y si $d$ divide a la vez a $b$ y a $r$, también divide a $a = q \times b + r$. Por tanto, las parejas $(a, b)$ y $(b, r)$ tienen exactamente los mismos divisores comunes y, por eso, el mismo MCD: $$\text{MCD}(a, b) = \text{MCD}(b, r)$$ Los números se hacen más pequeños en cada paso, así que el algoritmo siempre termina.

La imagen geométrica: cuadrados en un rectángulo de 48 por 18

Un rectángulo mide $48$ por $18$. Corta una y otra vez los cuadrados más grandes posibles. ¿Cuál es el lado de los cuadrados que encajan exactamente al final?

Corta cuadrados de lado 18 del lado largo: Caben dos cuadrados $18 \times 18$ y sobran $12$: $48 = 2 \times 18 + 12$ = Queda un rectángulo $18 \times 12$

Corta cuadrados de lado 12 del resto: Cabe un cuadrado $12 \times 12$ y sobran $6$: $18 = 1 \times 12 + 6$ = Queda un rectángulo $12 \times 6$

Corta cuadrados de lado 6: Caben exactamente dos cuadrados $6 \times 6$: $12 = 2 \times 6 + 0$ = No sobra nada

Cubre todo el rectángulo con el último cuadrado: $6$ divide a $48$ y a $18$: $\frac{48}{6} \times \frac{18}{6} = 8 \times 3$ = $24$ cuadrados de lado $6$ lo cubren

Answer: Los cuadrados de lado $6$ encajan exactamente, así que $\text{MCD}(48, 18) = 6$. Cada corte es una fila del algoritmo.

La versión con restas

Calcula $\text{MCD}(35, 14)$ usando solo restas: resta siempre el número menor del mayor.

Resta 14 a 35: $35 - 14 = 21$ = Nueva pareja $(21, 14)$

Resta 14 otra vez: $21 - 14 = 7$ = Nueva pareja $(14, 7)$

Ahora 7 es menor: resta 7: $14 - 7 = 7$ = Nueva pareja $(7, 7)$

Resta una vez más: $7 - 7 = 0$ = Los números se paran en $7$

Answer: $\text{MCD}(35, 14) = 7$. Restar $14$ dos veces es lo mismo que una división: $35 = 2 \times 14 + 7$. La división es solo un atajo de muchas restas.

Un clásico: el MCD de 1071 y 462

Calcula $\text{MCD}(1071, 462)$ con el algoritmo de Euclides.

Divide 1071 entre 462: $462 \times 2 = 924$ y $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Sustituye la pareja por (462, 147) y divide: $147 \times 3 = 441$ y $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Sustituye la pareja por (147, 21) y divide: $21 \times 7 = 147$, no sobra nada = $147 = 7 \times 21 + 0$

Lee el último resto distinto de cero: El resto fue $0$ al dividir entre $21$ = $\text{MCD}(1071, 462) = 21$

Answer: $\text{MCD}(1071, 462) = 21$. Comprobación: $1071 = 21 \times 51$ y $462 = 21 \times 22$.

Simplificar una fracción difícil

Simplifica $\frac{391}{667}$ hasta la fracción irreducible.

Divide 667 entre 391: $667 = 1 \times 391 + 276$ = Resto $276$

Divide 391 entre 276: $391 = 1 \times 276 + 115$ = Resto $115$

Divide 276 entre 115: $276 = 2 \times 115 + 46$ = Resto $46$

Divide 115 entre 46 y luego 46 entre 23: $115 = 2 \times 46 + 23$ y $46 = 2 \times 23 + 0$ = $\text{MCD}(391, 667) = 23$

Divide numerador y denominador entre 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Como $17$ y $29$ son primos, la fracción ya no se puede simplificar más.

El mcm a partir del MCD

Calcula $\text{mcm}(84, 120)$ con el algoritmo de Euclides.

Divide 120 entre 84: $120 = 1 \times 84 + 36$ = Resto $36$

Divide 84 entre 36: $84 = 2 \times 36 + 12$ = Resto $12$

Divide 36 entre 12: $36 = 3 \times 12 + 0$ = $\text{MCD}(84, 120) = 12$

Usa mcm = a × b ÷ MCD: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Comprueba: $840 \div 84 = 10$ y $840 \div 120 = 7$ = Los dos dividen a $840$

Answer: $\text{mcm}(84, 120) = 840$.

El algoritmo de Euclides tiene más de 2300 años (Euclides lo escribió hacia el 300 a. C.) y sigue siendo uno de los algoritmos más usados del mundo: - **Números grandes**: descomponer $1071$ o $391$ en factores primos es lento, pero tres o cuatro divisiones dan el MCD enseguida. Con números de cientos de cifras la factorización es prácticamente imposible, mientras que el algoritmo de Euclides termina en, como mucho, unos pocos miles de pasos rápidos. - **Fracciones**: para simplificar $\frac{391}{667}$ necesitas $\text{MCD}(391, 667) = 23$, que cuesta ver factorizando pero sale rápido con el algoritmo. - **mcm**: en cuanto conoces el MCD, $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$, así que un solo algoritmo te da los dos. - **Baldosas, engranajes y pantallas**: la baldosa cuadrada más grande para un suelo, cuándo dos engranajes vuelven a coincidir y por qué una pantalla de $1920 \times 1080$ es $16:9$ se reducen todos al MCD. - **Seguridad en internet**: sistemas de cifrado como RSA usan una versión ampliada de este algoritmo cada vez que abres una web segura.

Mistake: Quedarse con el número grande antiguo: tras $48 = 2 \times 18 + 12$, seguir con $48$ y $12$

Why: El algoritmo funciona porque $\text{MCD}(a, b) = \text{MCD}(b, r)$. El número $a$ ya no hace falta después de la primera división.

Correct: La siguiente pareja es $(18, 12)$: el divisor anterior y el resto. Así que $18 = 1 \times 12 + 6$.

Mistake: Dar $0$ o el último cociente como MCD

Why: La última fila tiene resto $0$, lo que solo indica que hay que parar. El cociente cuenta cuántos cuadrados caben, no es un divisor común.

Correct: El MCD es el último resto distinto de cero, el divisor de la última fila. En $12 = 2 \times 6 + 0$ es $6$.

Mistake: Escribir un resto demasiado grande, como $1071 = 1 \times 462 + 609$

Why: La igualdad es cierta, pero $609 > 462$, así que $462$ todavía cabe otra vez. El resto tiene que ser menor que el divisor.

Correct: Toma el mayor cociente posible: $1071 = 2 \times 462 + 147$ con $147 < 462$.

Mistake: Tomar $a \times b$ como mcm

Why: $a \times b$ siempre es un múltiplo común, pero normalmente no el mínimo: $84 \times 120 = 10080$ cuenta dos veces el divisor común $12$.

Correct: Divide entre el MCD: $\text{mcm}(84, 120) = \frac{84 \times 120}{12} = 840$.

Embaldosar un suelo con las baldosas cuadradas más grandes

Un alicatador quiere cubrir un suelo rectangular con baldosas cuadradas iguales sin cortar ninguna. El lado más grande posible es el MCD de las dos medidas.

Un panel de $48$ cm por $18$ cm se cubre exactamente con cuadrados de $6$ cm: $\text{MCD}(48, 18) = 6$, es decir, $8 \times 3 = 24$ baldosas.

Engranajes y ciclos que se repiten

Cuando dos ruedas dentadas giran juntas, los mismos dos dientes vuelven a encontrarse después de un número de dientes igual al mcm de sus dientes. El algoritmo de Euclides da el MCD y de ahí sale el mcm.

Ruedas de $18$ y $48$ dientes: $\text{MCD} = 6$, así que los mismos dientes vuelven a encontrarse tras $\frac{18 \times 48}{6} = 144$ dientes.

Proporción de las pantallas

Una resolución como $1920 \times 1080$ se convierte en una proporción dividiendo los dos números entre su MCD.

$1280 \times 1024$: $\text{MCD}(1280, 1024) = 256$, así que la proporción es $5:4$.

Algoritmo de Euclides: divide $a$ entre $b$ como $a = q \times b + r$ con $0 \le r < b$ y sustituye $(a, b)$ por $(b, r)$ hasta que el resto sea $0$

El MCD es el último resto distinto de cero, el divisor de la última fila

Funciona porque $\text{MCD}(a, b) = \text{MCD}(b, r)$: las dos parejas tienen los mismos divisores comunes

Geométricamente, corta un rectángulo $a \times b$ en los cuadrados más grandes posibles; el lado del último cuadrado es el MCD

La versión con restas resta una y otra vez el número menor; la división es su atajo

Sirve para simplificar fracciones, para calcular $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ y para saber si dos números son primos entre sí (MCD $= 1$)

Q: ¿Importa con qué número empiezo?

A: No. Si empiezas con el número menor delante, la primera fila es del tipo $18 = 0 \times 48 + 18$, que solo intercambia los dos números. Empezar con el mayor te ahorra ese paso.

Q: ¿Es el algoritmo de Euclides más rápido que la descomposición en factores primos?

A: Con números pequeños como $12$ y $18$ los dos métodos son rápidos. Con números grandes, sí, muchísimo: no necesitas encontrar ningún número primo. $\text{MCD}(1071, 462)$ necesita tres divisiones, mientras que la factorización exige $1071 = 3^2 \times 7 \times 17$ y $462 = 2 \times 3 \times 7 \times 11$.

Q: ¿Qué significa que el algoritmo termine con MCD 1?

A: Entonces los dos números son **primos entre sí** (coprimos): no tienen ningún divisor común salvo el $1$. Los números de Fibonacci vecinos, como $144$ y $89$, siempre son primos entre sí, y con ellos el algoritmo necesita el mayor número de pasos para su tamaño.

Q: ¿Puedo usarlo con tres números?

A: Sí, de dos en dos: $\text{MCD}(a, b, c) = \text{MCD}(\text{MCD}(a, b), c)$. Por ejemplo, $\text{MCD}(840, 1176) = 168$ y $\text{MCD}(168, 1260) = 84$, así que el MCD de los tres es $84$.

Salir de la presentación

Algoritmo de Euclides

1 / 14

Teoría de Números / Factores y Múltiplos

Algoritmo de Euclides

Calcula el máximo común divisor de dos números con divisiones sucesivas con resto y úsalo para simplificar fracciones y hallar el mcm.

Avanzado25 min

Usa las flechas o la barra espaciadora para navegar