Algoritmo de Euclides
Para 1071 y 462 el máximo común divisor es 21, al que se llega en tres divisiones: 1071 = 462 × 2 + 147, luego 462 = 147 × 3 + 21 y al final resto cero. Escriba dos enteros y vea cada paso. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- A
- 1 071
- B
- 462
- Gcd
- 21
- Número de pasos
- 3
La calculadora del algoritmo de Euclides toma dos enteros y calcula su máximo común divisor tal como lo describió Euclides hace más de dos mil años: dividiendo repetidamente y quedándose con el resto. En lugar de devolver solo el número final, devuelve la lista completa de pasos —cada línea de la forma dividendo = divisor × cociente + resto— para que pueda ver exactamente cómo se llegó a la respuesta. Acepta valores negativos (el MCD usa valores absolutos), rechaza entradas no enteras y se niega a calcular el caso indefinido mcd(0,0).
Qué hace realmente el algoritmo de Euclides
El máximo común divisor de dos enteros es el número más grande que divide a ambos sin dejar resto. El algoritmo de Euclides lo encuentra sin factorizar nada, y por eso sigue siendo rápido incluso con entradas muy grandes. La idea es sencilla: si un número divide tanto a a como a b, también divide al resto de dividir a entre b.
Así que se sustituye la pareja (a, b) por (b, a mod b) y se repite. Cada paso es una división larga —por ejemplo, 1071 = 462 × 2 + 147— y se continúa hasta que el resto es cero. El último resto distinto de cero es el MCD.
Como el resto se reduce estrictamente en cada paso, el bucle termina siempre, y termina rápido: el número de pasos es proporcional al logaritmo de la entrada menor.
Entradas, casos límite y cómo se informan los errores
Usted envía dos campos, a y b, y ambos deben ser enteros. Los enteros negativos son válidos: el MCD se define sobre valores absolutos, de modo que mcd(-1071, 462) es lo mismo que mcd(1071, 462), y la lista de pasos se calcula sobre los valores absolutos. El cero es una entrada válida para uno de los campos —mcd(a, 0) es |a|, y en ese caso la lista de pasos está vacía porque no hace falta ninguna división—, pero que ambos campos sean cero se rechaza, porque mcd(0,0) está matemáticamente indefinido.
Los errores nunca producen una respuesta parcial: la petición se rechaza con un código legible por máquina y un mensaje que puede mostrar al usuario.
Dónde resulta útil un MCD paso a paso
El MCD a secas es una mercancía común: todos los lenguajes lo tienen en su biblioteca estándar. Lo que añade esta capacidad es la traza. Profesores y estudiantes usan la lista de pasos para verificar que un ejercicio se resolvió con el algoritmo de Euclides de verdad y no adivinando divisores.
Los desarrolladores la usan al depurar simplificación de fracciones, reducción de proporciones de aspecto o comprobaciones de coprimalidad, porque ver 252 = 105 × 2 + 42 señala exactamente dónde diverge un cálculo a mano del código. Quienes aprenden criptografía se encuentran con el algoritmo como base de la versión extendida que produce los coeficientes de Bézout y los inversos modulares; ver primero los pasos de división sencillos facilita mucho ese salto.
Qué puede hacer con ella
Corregir un ejercicio resuelto
Pegue los dos números de un problema de deberes y compare sus pasos de división escritos con los que el algoritmo produce realmente.
Simplificar fracciones y proporciones
Obtenga el MCD de un numerador y un denominador para reducir una fracción, con la lista de pasos como pista de auditoría de cómo se halló el divisor.
Enseñar el algoritmo antes de la versión extendida
Muestre primero a los estudiantes la traza de división sencilla y pase después a los coeficientes de Bézout y los inversos modulares construidos sobre el mismo bucle.
Preguntas frecuentes
¿Cuánto cuesta?
También es gratis ejecutarlo en su navegador en esta página.
¿Por qué rechaza mcd(0,0)?
Porque el máximo común divisor de cero y cero está indefinido: todo entero divide a cero, así que no hay ninguno que sea el mayor. Proporcione al menos un valor distinto de cero.
¿Puedo pasar números negativos?
Sí. El MCD se calcula sobre valores absolutos, de modo que mcd(-1071, 462) devuelve el mismo resultado que mcd(1071, 462).
¿Qué contiene el array steps?
Un objeto por división: dividendo, divisor, cociente y resto, de modo que cada línea se lee dividendo = divisor × cociente + resto. El último resto distinto de cero es el MCD.
¿Qué tan grandes pueden ser las entradas?
Hasta el entero seguro máximo, 9007199254740991, de modo que cada cociente y cada resto de la salida es exacto.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su stack
curl -X POST https://api.kit.forhosting.com/math/euclidean-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":1071,"b":462}'const res = await fetch("https://api.kit.forhosting.com/math/euclidean-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 1071,
"b": 462
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/euclidean-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 1071,
"b": 462
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/euclidean-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":1071,"b":462}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":1071,"b":462}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/euclidean-algorithm", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Ejemplo de solicitud
{
"a": 1071,
"b": 462
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.euclidean_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Límites
max_abs | 9007199254740991 |
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
El mismo código se ejecuta gratis en su navegador en esta página y a través de la API de pago.
Qué hace realmente el algoritmo de Euclides
Este endpoint ejecuta exactamente ese procedimiento y le devuelve cada división realizada, no solo la conclusión, lo que lo hace útil tanto para corregir deberes como para auditar un cálculo dentro de un sistema mayor.
Entradas, casos límite y cómo se informan los errores
Se aceptan cadenas numéricas que representan enteros exactos, como "1071"; los decimales, las fracciones, la notación científica y los valores no numéricos se rechazan con un error invalid_input que explica qué falló. Los valores están acotados por el rango de enteros seguros de los dobles IEEE 754, unos 9 cuatrillones, de modo que cada cociente y cada resto de la salida es exacto.
Preguntas técnicas
¿Qué cuenta como entero?
Un número JSON sin parte fraccionaria, o una cadena de dígitos con un signo inicial opcional. Los decimales, la notación científica y los valores no numéricos se rechazan con un error invalid_input.