¿Qué es el máximo común divisor, en una frase?

El mayor número entero que divide a los dos números de forma exacta, sin dejar resto. Para 1071 y 462 es 21: 1071 = 21 × 51 y 462 = 21 × 22, y 51 y 22 no comparten ningún factor, que es lo que hace que 21 sea el máximo. Fíjate en que 3 y 7 también dividen a los dos números: son divisores comunes, solo que no el mayor. El resultado principal de la página es siempre ese número, y los pasos que aparecen debajo son la prueba.

¿Por qué el último paso termina siempre en + 0?

Porque un resto igual a cero es lo único que detiene el algoritmo. El bucle sustituye la pareja por una más pequeña —el segundo número y el resto— y los números caen en cada ronda, así que tarde o temprano tienen que llegar a cero. 147 = 7 * 21 + 0 es la ronda en la que eso ocurre, y el máximo común divisor es el divisor de esa ronda, 21. La página la imprime en lugar de esconderla porque una lista de pasos que se detuviera en el último resto distinto de cero dejaría al lector el trabajo de deducir que la búsqueda había terminado.

¿Importa el orden en que escribo los dos números?

No. La página los pone en orden descendente antes de la primera ronda, así que 462 y 1071 producen exactamente las mismas tres líneas que 1071 y 462. Eso es una decisión y no una propiedad del algoritmo —la regla mcd(a, b) = mcd(b, a) hace que cualquier orden dé la respuesta correcta—, pero sin ordenarlos la primera línea sería 3 = 0 * 5 + 3 para la pareja 3 y 5, que es una división legal pero se lee como si dividir un número pequeño entre uno mayor formara parte del método. Es también la razón de que las casillas se llamen primer número y segundo número y no dividendo y divisor: esos dos papeles se intercambian en cada ronda.

¿Qué significa una respuesta de 1?

Que los dos números no comparten ningún factor por encima de 1, lo cual es una respuesta completa y no un fracaso. A esos números se les llama coprimos, y la pareja 9 y 20 de esta página es un ejemplo. También dice algo práctico: la fracción 9/20 ya está en su forma irreducible, así que no hay ninguna simplificación disponible. A medida que los números crecen, las parejas coprimas pasan a ser el caso habitual, y por eso el método importa en criptografía: construir una clave RSA significa encontrar números que no compartan ningún factor con uno dado.

¿Los números más grandes necesitan siempre más rondas?

No, y la tabla de referencia está ahí para hacerlo concreto. 1000000 y 999998 terminan en dos rondas, mientras que 610 y 377, con tres cifras cada uno, necesitan trece. Lo que obliga a muchas rondas no es el tamaño sino la lentitud con que encogen los números, y las parejas que encogen más despacio son las de números de Fibonacci consecutivos, donde cada resto se acerca mucho al divisor. Ese resultado es el teorema de Lamé, y pone un techo al número de rondas que crece solo con el número de cifras, que es la razón de que el algoritmo se considere rápido.

¿En qué se diferencia de descomponer los dos números en factores?

En que descomponer cuesta mucho más trabajo, y es un trabajo que esta página no hace nunca. Para descomponer 1071 por divisiones sucesivas habría que probar divisores hasta su raíz cuadrada, unos 32; el algoritmo en cambio divide un número entre otro que ya tiene, y termina en tres rondas. Con números pequeños como estos la diferencia es invisible, pero descomponer se vuelve dramáticamente más difícil a medida que los números crecen mientras que el algoritmo de Euclides apenas lo nota. Esa distancia es la razón entera de que se siga enseñando, y también la razón de que la respuesta salga del bucle y no de un segundo cálculo: hacer los dos arriesgaría que los pasos impresos no coincidieran con el número impreso encima de ellos. Y es que aquí no hay división larga en el sentido del galón de toda la vida: lo que se imprime son ecuaciones.

Calculadora del algoritmo de Euclides

Resultado

Máximo común divisor

Paso a paso: 1071 = 2 * 462 + 147; 462 = 3 * 147 + 21; 147 = 7 * 21 + 0

El algoritmo de Euclides halla el máximo común divisor de dos números enteros sin descomponer ninguno de los dos en factores. Se apoya en un solo hecho: si a = q * b + r, entonces todo lo que divide a la vez a a y a b divide también a r, y todo lo que divide a la vez a b y a r divide también a a; por tanto la pareja (a, b) y la pareja (b, r) tienen exactamente los mismos divisores comunes. Se sustituye la pareja por la pequeña y se repite. En cada ronda los números encogen, y como no pueden encoger para siempre, uno de ellos acaba valiendo cero; el otro es la respuesta. Para 1071 y 462 las rondas son 1071 = 2 * 462 + 147, después 462 = 3 * 147 + 21 y por último 147 = 7 * 21 + 0, así que el máximo común divisor es 21. Tres rondas, dos restas hechas por múltiplos y ninguna descomposición en factores por ningún lado. Ese último punto es la razón de que merezca la pena conocer el método y no solo usarlo: para hallar los factores de un número grande habría que probar divisores hasta su raíz cuadrada, mientras que este método solo divide un número entre otro que ya tiene en la mano, y los números caen deprisa. La pareja 610 y 377, dos números de Fibonacci consecutivos, es el peor caso que existe, y aun así termina en trece rondas con números de tres cifras cada uno. El número de rondas no lo fija el tamaño de los números. 1000000 y 999998 son mucho mayores que 610 y 377 y terminan en dos rondas, porque el segundo paso cae en un múltiplo exacto; en cambio 610 y 377 necesitan trece. La pareja que más rondas consume para su tamaño es siempre una pareja de números de Fibonacci consecutivos, un resultado que tiene nombre propio, el teorema de Lamé, y es la razón de que el número de rondas tenga su propia columna en la tabla de abajo. Los dos números pueden darse en cualquier orden. Ponerlos en orden descendente antes de empezar es una decisión de esta página y no una exigencia del método, y es lo que hace que 462 y 1071 impriman exactamente las mismas tres líneas que 1071 y 462. Los pasos se escriben como ecuaciones y no como una división larga: cada ronda es a = q * b + r, con puntos y coma entre ronda y ronda. Lee una ronda como una frase —1071 es 2 veces 462 más 147— y la ronda siguiente es esa misma frase con los papeles desplazados: 462 es 3 veces 147 más 21. El resto de una ronda se convierte en el divisor de la siguiente, y el divisor se convierte en el dividendo.

Tres parejas pasadas por el algoritmo, con el número de rondas que necesita cada una

Primer número	Segundo número	Rondas	MCD
1071	462	3	21
48	180	3	12
36	36	1	36

Las dos columnas de la derecha son las que merece la pena leer juntas, porque no se mueven a la vez. Las dos primeras filas necesitan tres rondas cada una y la tercera necesita una, pero mira mejor la columna de la respuesta: 36 y 36 dan 36 en una sola ronda, mientras que 48 y 180 dan 12 en tres, y 1071 y 462 dan 21 en tres. El tamaño no dice nada de ninguno de los dos números. Una pareja más grande no es un cálculo más largo, y un cálculo más largo no significa una respuesta más grande. La columna de rondas enseña por qué: 36 y 36 colapsan de inmediato porque el segundo número divide al primero de forma exacta, así que el bucle se detiene en su primera pasada, mientras que 48 y 180 bajan hasta 36 y después hasta 12 sin que ninguno de esos pasos sea exacto. El peor caso en general es una pareja de números de Fibonacci consecutivos, y por eso el ejemplo resuelto de la página de arriba usa 1071 y 462, la pareja con la que se suele enseñar el algoritmo, en lugar de una pareja mayor que terminaría antes.

Fórmula

a = q * b + r, por lo que mcd(a, b) = mcd(b, r); se repite hasta que r = 0, y entonces b es la respuesta

a = q * b + r: Una ronda del algoritmo, escrita como una ecuación. a es el mayor de los dos números en esa ronda, b el menor, q es cuántas veces enteras cabe b en a y r es lo que sobra. Esta es exactamente la notación de los pasos de la página: 1071 = 2 * 462 + 147 es una ronda
a, b: Los dos números que se comparan. Cambian de identidad en cada ronda: la b de una ronda pasa a ser la a de la siguiente, y la r se convierte en la nueva b. Ese intercambio es la razón de que las casillas de entrada no se llamen dividendo y divisor: en la primera ronda el dividendo es 1071, en la segunda es 462, y una etiqueta que acierta en una ronda falla en las demás
q: El cociente, cuántas veces enteras cabe b en a. Siempre vale al menos 1, porque la pareja se pone en orden descendente antes de que arranque el bucle, y por eso aquí no se ve nunca q = 0. La única ronda en la que q no llama la atención es la última, donde el resto es cero y el cociente es exacto
r: El resto, siempre menor que b y nunca negativo. La regla de parada del algoritmo es r = 0, y se imprime como la última ronda en lugar de omitirse: 147 = 7 * 21 + 0 es la línea que dice que la búsqueda ha terminado y que la respuesta es 21
gcd(a, b): El máximo común divisor: el mayor número entero que divide a la vez a a y a b de forma exacta. La respuesta es la b de la ronda final, tomada directamente del bucle y no recalculada. Para 1071 y 462 es 21, y por eso 1071 = 21 × 51 y 462 = 21 × 22, y ningún número mayor divide a los dos
610 = 1 * 377 + 233: La ronda inicial del peor caso: dos números de Fibonacci consecutivos. Aquí todos los cocientes valen 1 y los números apenas encogen, que es lo que hace que esta pareja necesite trece rondas. El teorema de Lamé dice que ninguna pareja de números de este tamaño puede necesitar más

Simplificar una fracción es el uso de todos los días. Para escribir 462/1071 en su forma irreducible hace falta el máximo común divisor de los dos, y esta página te lo da junto con la prueba: 21, y las tres rondas que lo han producido. Dividiendo arriba y abajo entre 21 queda 22/51, y los pasos impresos son lo que permite comprobar la simplificación en lugar de fiarse de ella. La misma necesidad aparece siempre que hay que reducir una razón: relaciones de transmisión, proporciones de pantalla, planos a escala y dos medidas cualesquiera que se quieran expresar como proporción y no como una pareja de números. El segundo uso está en el código y en las clases, donde el algoritmo se enseña como el primer algoritmo interesante: termina, es rápido y es correcto por una razón que se ve en una sola ecuación. Es también la manera estándar de calcular un inverso modular —la versión extendida arrastra dos números extra por las mismas rondas—, que es el paso que hay dentro de la generación de claves RSA. Un tercer uso es como comprobación rápida antes de descomponer en factores. Descubrir que 1071 es 3 × 357 y que 462 es 2 × 3 × 7 × 11 cuesta trabajo; descubrir que su máximo común divisor es 21 son tres divisiones, así que pasar antes por esta página dice si la simplificación va a ser fácil antes de empezar. Cuando solo se quiere la respuesta y no el proceso, gcf-calculator plantea la misma pregunta en una forma más corta y admite más de dos números a la vez; lcm-calculator usa el divisor para obtener el mínimo común múltiplo, ya que mcm = (a / mcd) * b; y remainder-calculator cubre qué significa un resto cuando los números pueden ser negativos, cosa que esta página nunca tiene que tratar.

Ejemplos resueltos

La pareja de manual: 1071 y 462
1. ¿Cuántas veces cabe 462 en 1071? Dos, y 2 × 462 = 924, así que sobran 1071 − 924 = 147
2. Ahora la pareja es 462 y 147: 147 cabe tres veces en 462, 3 × 147 = 441, y sobran 21
3. Ahora la pareja es 147 y 21: 21 cabe exactamente siete veces en 147 y no sobra nada
4. El resto es cero, así que el algoritmo se detiene y la respuesta es 21
Es la entrada por defecto y el ejemplo con el que se suele presentar este algoritmo. Merece la pena hacerle dos comprobaciones al resultado. Divide los dos números entre 21 y salen 51 y 22, que no comparten ningún factor, y eso es lo que hace que 21 sea el máximo y no simplemente un divisor común. Y fíjate en que aquí no ha habido ninguna descomposición en factores: para hallar los factores de 1071 por divisiones sucesivas habría que subir hasta 32, mientras que el algoritmo solo ha dividido un número entre otro que ya tenía en la mano. Tres rondas, cada una más barata que la anterior.
Una sola ronda basta: 12 y 60
1. Pon la pareja en orden descendente: 60 primero, 12 después
2. 60 = 5 × 12 + 0, así que 12 divide a 60 de forma exacta
3. El resto es cero de inmediato, así que el algoritmo se detiene tras una sola ronda
4. La respuesta es 12, el menor de los dos, porque divide al mayor
Es la ejecución no trivial más corta posible y el caso que enseña por qué la última ronda se imprime en lugar de saltarse. La línea 60 = 5 * 12 + 0 es toda la respuesta: dice que el resto llegó a cero, que es la única manera que tiene este algoritmo de pararse. Quita esa línea y los pasos quedarían vacíos, y quien los leyera no tendría forma de distinguir una respuesta de una sola ronda de una página que no se ha ejecutado. Siempre que un número divide al otro de forma exacta, el máximo común divisor es sencillamente el menor de los dos.
Números coprimos: 9 y 20
1. 20 = 2 × 9 + 2, así que la pareja pasa a ser 9 y 2
2. 9 = 4 × 2 + 1, así que la pareja pasa a ser 2 y 1
3. 2 = 2 × 1 + 0, así que el algoritmo se detiene
4. La respuesta es 1, lo que significa que 9 y 20 no comparten ningún factor por encima de 1
Un máximo común divisor de 1 es una respuesta de verdad y no un fallo, y tiene nombre: los números son coprimos. Es también la señal de que la fracción 9/20 ya está en su forma irreducible, así que no hay ninguna simplificación disponible. Fíjate en que las rondas no se han colapsado: el algoritmo ha bajado hasta 1 en tres pasos, porque ninguno de los dos números dividió al otro de forma exacta. Las parejas coprimas son el caso habitual a medida que los números crecen: la probabilidad de que dos números elegidos al azar compartan un factor se desvanece deprisa, y eso es justo lo que hace útil el método para construir un inverso modular en criptografía.

Limitaciones

Los dos números tienen que ser enteros, y los dos tienen que estar entre 1 y 1000000. El cero se rechaza en lugar de tratarse como un caso especial. El máximo común divisor de a y 0 es a, que es una respuesta perfectamente válida, pero esta página no puede mostrarla: la primera ronda sería a = q * 0 + r, y ese q no existe. En lugar de imprimir un proceso con un agujero, la página rechaza la entrada. Los números negativos se rechazan por la misma razón: los pasos tal como se imprimen dan por supuesto que los dos números valen al menos 1, y un operando negativo necesitaría una regla sobre qué significan el cociente y el resto que esta página no enuncia en ninguna parte. El techo de 1000000 no tiene que ver con el algoritmo, que funcionaría encantado con números mucho mayores: está ahí para que todas las restas, multiplicaciones y restos del camino sean exactos en aritmética de coma flotante de doble precisión, y para que los pasos impresos no puedan alcanzar una longitud que deje de ser legible. Dos números bastante pequeños pueden producir muchas rondas —610 y 377 necesitan trece—, pero el número de rondas está limitado en la práctica por ese techo, y la tabla de referencia tiene una columna de rondas precisamente para que se vea variar. Los pasos se imprimen como ecuaciones —a = q * b + r, separadas por puntos y coma— y no como una división larga, así que quien busque el galón de la división de toda la vida no lo va a encontrar aquí. Los dos operandos son intercambiables: la página los ordena de mayor a menor antes de empezar, así que no sirve para ver cómo sería 3 = 0 * 5 + 3, porque esa ronda no se produce nunca. Si tus números pueden ser negativos, o si quieres que se explicite la convención del resto, remainder-calculator es la página para esa pregunta.

Preguntas frecuentes

¿Qué es el máximo común divisor, en una frase?: El mayor número entero que divide a los dos números de forma exacta, sin dejar resto. Para 1071 y 462 es 21: 1071 = 21 × 51 y 462 = 21 × 22, y 51 y 22 no comparten ningún factor, que es lo que hace que 21 sea el máximo. Fíjate en que 3 y 7 también dividen a los dos números: son divisores comunes, solo que no el mayor. El resultado principal de la página es siempre ese número, y los pasos que aparecen debajo son la prueba.
¿Por qué el último paso termina siempre en + 0?: Porque un resto igual a cero es lo único que detiene el algoritmo. El bucle sustituye la pareja por una más pequeña —el segundo número y el resto— y los números caen en cada ronda, así que tarde o temprano tienen que llegar a cero. 147 = 7 * 21 + 0 es la ronda en la que eso ocurre, y el máximo común divisor es el divisor de esa ronda, 21. La página la imprime en lugar de esconderla porque una lista de pasos que se detuviera en el último resto distinto de cero dejaría al lector el trabajo de deducir que la búsqueda había terminado.
¿Importa el orden en que escribo los dos números?: No. La página los pone en orden descendente antes de la primera ronda, así que 462 y 1071 producen exactamente las mismas tres líneas que 1071 y 462. Eso es una decisión y no una propiedad del algoritmo —la regla mcd(a, b) = mcd(b, a) hace que cualquier orden dé la respuesta correcta—, pero sin ordenarlos la primera línea sería 3 = 0 * 5 + 3 para la pareja 3 y 5, que es una división legal pero se lee como si dividir un número pequeño entre uno mayor formara parte del método. Es también la razón de que las casillas se llamen primer número y segundo número y no dividendo y divisor: esos dos papeles se intercambian en cada ronda.
¿Qué significa una respuesta de 1?: Que los dos números no comparten ningún factor por encima de 1, lo cual es una respuesta completa y no un fracaso. A esos números se les llama coprimos, y la pareja 9 y 20 de esta página es un ejemplo. También dice algo práctico: la fracción 9/20 ya está en su forma irreducible, así que no hay ninguna simplificación disponible. A medida que los números crecen, las parejas coprimas pasan a ser el caso habitual, y por eso el método importa en criptografía: construir una clave RSA significa encontrar números que no compartan ningún factor con uno dado.
¿Los números más grandes necesitan siempre más rondas?: No, y la tabla de referencia está ahí para hacerlo concreto. 1000000 y 999998 terminan en dos rondas, mientras que 610 y 377, con tres cifras cada uno, necesitan trece. Lo que obliga a muchas rondas no es el tamaño sino la lentitud con que encogen los números, y las parejas que encogen más despacio son las de números de Fibonacci consecutivos, donde cada resto se acerca mucho al divisor. Ese resultado es el teorema de Lamé, y pone un techo al número de rondas que crece solo con el número de cifras, que es la razón de que el algoritmo se considere rápido.
¿En qué se diferencia de descomponer los dos números en factores?: En que descomponer cuesta mucho más trabajo, y es un trabajo que esta página no hace nunca. Para descomponer 1071 por divisiones sucesivas habría que probar divisores hasta su raíz cuadrada, unos 32; el algoritmo en cambio divide un número entre otro que ya tiene, y termina en tres rondas. Con números pequeños como estos la diferencia es invisible, pero descomponer se vuelve dramáticamente más difícil a medida que los números crecen mientras que el algoritmo de Euclides apenas lo nota. Esa distancia es la razón entera de que se siga enseñando, y también la razón de que la respuesta salga del bucle y no de un segundo cálculo: hacer los dos arriesgaría que los pasos impresos no coincidieran con el número impreso encima de ellos. Y es que aquí no hay división larga en el sentido del galón de toda la vida: lo que se imprime son ecuaciones.

Referencias

Euclidean Algorithm — la recurrencia gcd(a, b) = gcd(b, a mod b), la demostración de que termina y su relación con las fracciones continuas — Wolfram MathWorld (United States)
Greatest Common Divisor — qué es el máximo común divisor y por qué gcd(a, 0) = a es el caso base en el que se detiene el algoritmo — Wolfram MathWorld (United States)
El algoritmo de Euclides — el método paso a paso para calcular el mcd de dos números enteros, con el ejemplo mcd(20, 16) = 4 — Sangakoo (España)
Lamé's Theorem — el resultado de que la pareja que más rondas consume para su tamaño es siempre una pareja de números de Fibonacci consecutivos — Wolfram MathWorld (United States)

Calculadoras relacionadas

Calculadora de MCDMáximo común divisor de dos o más números, con los pasos.Calculadora de MCMMínimo común múltiplo de dos o más números.Calculadora de restoCociente y resto de una división, entera o decimal.Calculadora de menor a mayorOrdena números, decimales o fracciones de menor a mayor.Calculadora de móduloEl resto de una división (operación módulo).