Calculadora del MCD con el Algoritmo de Euclides

Ingresar cálculo

Valor 1

Valor 2

Resultados

https://example.com

Máximo común divisor

4

MCD (máximo común divisor)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

¿Qué es el algoritmo de Euclides?

El máximo común divisor (MCD), conocido en inglés como GCF o GCD, es el mayor número entero que divide de forma exacta a dos enteros. El algoritmo de Euclides es un método antiguo y sorprendentemente eficiente para calcularlo mediante divisiones sucesivas con resto. Esta calculadora te da el MCD de cualquier par de números enteros y muestra cada paso de la división para que puedas seguir todo el proceso.

El algoritmo de Euclides recubre un rectángulo con los cuadrados iguales más grandes posibles; el lado de ese cuadrado es el MCD.

Cómo usarla

Introduce dos números enteros en Valor 1 y Valor 2. La herramienta toma el mayor como dividendo y el menor como divisor, y va dividiendo de forma repetida hasta que el resto sea cero. El último divisor distinto de cero es el MCD. El orden no influye y los signos negativos se ignoran, ya que el MCD solo depende del valor absoluto.

La fórmula explicada

En cada paso se calcula un cociente y un resto: \(a = c \times b + R\), donde \(c = \text{parte entera de } (a / b)\) y \(R = a \bmod b\). Después se sustituye a por b y b por R, y se repite. Como cada resto es estrictamente menor que el divisor anterior, el proceso siempre termina. Cuando R = 0, el divisor actual es la respuesta. Expresado como recursión:

$$\gcd(a, b) = \gcd\!\left(b,\ a \bmod b\right),\quad \gcd(a, 0) = a$$

Publicidad

Ejemplo resuelto

Calculemos el MCD(816, 2260). Tomamos a = 2260 y b = 816.

$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$

El resto llega a cero con el divisor 4, así que MCD(816, 2260) = 4.

Cada paso reemplaza (a, b) por (b, a mod b) hasta que el resto es 0; el último divisor distinto de cero es el MCD.

Preguntas frecuentes

¿Son lo mismo el MCD y el «greatest common divisor»? Sí. «Máximo común divisor» (MCD) equivale a «greatest common factor» (GCF) y «greatest common divisor» (GCD) en inglés; esta herramienta responde a todos ellos.

¿Qué pasa si uno de los datos es 0? \(\gcd(a, 0) = a\), porque cualquier número divide al 0. Si ambos valen 0, el MCD no está definido.

¿Puedo hallar el MCD de tres números? Aplica la herramienta por parejas: \(\gcd(x, y, z) = \gcd\!\left(\gcd(x, y),\ z\right)\).