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

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$.

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

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.

¿Puedo usarlo con tres números?

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$.

Recursos para profesores

Algoritmo de Euclides

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

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.

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 minLección

Compartir en Classroom

Ficha imprimible

Definición

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)

(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.

Pruébalo ahora

En el algoritmo de Euclides escribes

a = q \times b + r

con

0 \le r < b

. ¿Qué pareja divides a continuación?

Ejemplos resueltos

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

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

Errores comunes

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

Por qué está mal: 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.

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

Dar $0$ o el último cociente como MCD

Por qué está mal: 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.

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

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

Por qué está mal: La igualdad es cierta, pero $609 > 462$ , así que $462$ todavía cabe otra vez. El resto tiene que ser menor que el divisor.

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

Tomar $a \times b$ como mcm

Por qué está mal: $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$ .

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

Visual interactivo

Los cuadrados más grandes en un rectángulo: elige una pareja

Primer númeroSegundo número

Rectángulo 1071 × 462

Pulsa Siguiente paso para cortar los cuadrados más grandes que quepan.

Te toca: escribe el cociente y el resto de cada fila

Primer númeroSegundo número

Rectángulo 168 × 120

¿Cuántas veces cabe 120 en 168 y cuánto sobra?

168 =× 120 +

Sandbox interactivo

Calculadora de expresiones

Prueba estos:

Historial

Aún no hay cálculos

Problemas de práctica

18 problemas

Problema 1 de 18

Fácil

En el algoritmo de Euclides escribes

a = q \times b + r

con

0 \le r < b

. ¿Qué pareja divides a continuación?

Por qué es importante

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.

Aplicaciones del mundo real

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.

Ejemplo:

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.

1Inténtalo tú mismo

El suelo de un pasillo mide $168$ cm por $120$ cm. Hay que cubrirlo con baldosas cuadradas iguales, sin cortes y sin huecos.

¿Cuál es el lado, en cm, de la baldosa cuadrada más grande que sirve?

Paso 1: Escribe la expresión matemática

Calcula $\text{MCD}(168, 120)$ con el algoritmo de Euclides:

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.

Ejemplo:

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.

2Inténtalo tú mismo

El plato de una bicicleta tiene $84$ dientes y un piñón pequeño tiene $36$ dientes. Ahora se tocan dos dientes marcados.

¿Después de cuántos dientes vuelven a tocarse los dos dientes marcados?

Paso 1: Escribe la expresión matemática

Calcula $\text{mcm}(84, 36) = \frac{84 \times 36}{\text{MCD}(84, 36)}$ :

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.

Ejemplo:

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

3Inténtalo tú mismo

Un monitor tiene $1920$ por $1080$ píxeles. Para escribir su proporción, divides los dos números entre su MCD.

¿Cuánto vale $\text{MCD}(1920, 1080)$ ?

Paso 1: Escribe la expresión matemática

Aplica el algoritmo de Euclides a $1920$ y $1080$ :

Puntos clave

1Algoritmo 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$
2El MCD es el último resto distinto de cero, el divisor de la última fila
3Funciona porque $\text{MCD}(a, b) = \text{MCD}(b, r)$ : las dos parejas tienen los mismos divisores comunes
4Geométricamente, corta un rectángulo $a \times b$ en los cuadrados más grandes posibles; el lado del último cuadrado es el MCD
5La versión con restas resta una y otra vez el número menor; la división es su atajo
6Sirve 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$ )

Preguntas frecuentes

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.

Glosario

Algoritmo de Euclides: Método para el MCD de dos números: dividir con resto, sustituir la pareja por (divisor, resto) y repetir hasta que el resto sea $0$
División con resto: Escribir $a = q \times b + r$ con $0 \le r < b$ , por ejemplo $1071 = 2 \times 462 + 147$
Cociente: El número $q$ de veces enteras que $b$ cabe en $a$
Resto: El número $r$ que sobra tras la división, siempre menor que el divisor
Primos entre sí (coprimos): Dos números cuyo MCD es $1$ , como $144$ y $89$
Mínimo común múltiplo (mcm): El menor número positivo que es múltiplo de los dos números; $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$

Tarjeta de fórmulas

División con resto

a = q \times b + r, \quad 0 \le r < b

Una fila del algoritmo: $q$ es el cociente y $r$ el resto

Paso clave

\text{MCD}(a, b) = \text{MCD}(b, r)

Sustituye la pareja por (divisor, resto) y repite hasta que $r = 0$

mcm a partir del MCD

\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}

Multiplica los números y divide entre su MCD

Números primos entre sí

\text{MCD}(a, b) = 1

Los números no tienen ningún divisor común salvo el $1$

Reto de hoyUn problema, tres intentos

Más sobre este tema

Definición

Ejemplos resueltos

Errores comunes

Visual interactivo

Sandbox interactivo

Calculadora de expresiones

Historial

Problemas de práctica

Por qué es importante

Aplicaciones del mundo real

Embaldosar un suelo con las baldosas cuadradas más grandes

Engranajes y ciclos que se repiten

Proporción de las pantallas

Puntos clave

Preguntas frecuentes

Glosario

Tarjeta de fórmulas

División con resto

Paso clave

mcm a partir del MCD

Números primos entre sí

Más sobre este tema

Factores y múltiplos

Factorización prima

Números primos y compuestos

Máximo Común Divisor (MCD)