Euclides extendido: mcd y coeficientes de Bézout x, y
Para 240 y 46 el máximo común divisor es 2, y 240 × (−9) + 46 × 47 = 2. Escriba dos enteros y obtenga su divisor común, los dos coeficientes de Bézout y la igualdad que lo demuestra. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- Primer entero
- 240
- Segundo entero
- 46
- MCD
- 2
- X
- -9
- Y
- 47
- Comprobación
- 2
El algoritmo de Euclides extendido no solo informa del máximo común divisor de dos enteros: también produce coeficientes de Bézout x e y tales que a por x más b por y iguala ese mcd. Esos coeficientes aparecen en inversos modulares cuando el mcd es uno, en demostraciones constructivas de ecuaciones diofánticas lineales y en tareas de criptografía que necesitan una combinación explícita en lugar de un resto desnudo.
De restos a coeficientes de Bézout
La división euclídea ordinaria sustituye repetidamente un par (a, b) por (b, a mod b) hasta que el resto es cero; el último resto no nulo es mcd(a, b). La forma extendida registra cómo cada resto se escribe como combinación lineal entera de las entradas originales. En cada paso el resto actual es a por un coeficiente más b por otro, y al detenerse el algoritmo esos coeficientes son exactamente los números de Bézout del mcd.
Las presentaciones de aula suelen usar sustitución hacia atrás desde la secuencia de cocientes; el código de producción suele actualizar de forma iterativa dos pares de coeficientes sin guardar una pila de restos. Ambos enfoques calculan el mismo objeto matemático: enteros x e y que satisfacen a*x + b*y = mcd(a, b). Este extremo implementa la ruta iterativa sobre valores absolutos y luego reintroduce signos para que las entradas negativas sigan cumpliendo la identidad.
El mcd se devuelve siempre como entero no negativo, según la convención estándar de bibliotecas y enunciados de concurso.
Qué envía usted y qué recibe
El par cero y cero también se rechaza, porque mcd(0, 0) es indefinido y ningún coeficiente produce una ecuación significativa. En caso de éxito la respuesta incluye a y b normalizados, mcd, x, y, un objeto bezout anidado con los mismos coeficientes, una comprobación numérica igual a a*x + b*y y una cadena de ecuación como 240*(-9) + 46*(47) = 2.
Comprobaciones típicas: para 240 y 46 el mcd es 2 y una solución válida es x igual a menos nueve con y igual a cuarenta y siete; para un par primo con mcd uno los coeficientes dan un inverso modular de a módulo b tras reducir x. Casos límite con un cero y un compañero no nulo producen mcd igual al valor absoluto de la entrada no nula y un patrón de coeficientes trivial.
Dónde aparecen los coeficientes de Bézout en la práctica
Los programadores de concursos resuelven ax + by = c calculando primero el mcd y los coeficientes base, luego escalando y parametrizando la solución general cuando el mcd divide a c. Los estudiantes de criptografía recuperan inversos modulares para ejemplos RSA de juguete y cifrados afines cuando mcd(a, m) es uno leyendo el coeficiente de a tras la reducción módulo m. Los docentes asignan demostraciones constructivas de que dos enteros son coprimos y necesitan un oráculo determinista que muestre la combinación, no solo un bit de coprimalidad.
Ingenieros de datos y sistemas a veces necesitan combinaciones lineales explícitas al conciliar horarios periódicos o aritmética de pasos. Use la herramienta del navegador para comprobar tareas con rapidez y luego automatice el mismo contrato cuando su servicio necesite comprobaciones diofánticas masivas. Si solo necesita el mcd sin coeficientes, esta página sigue respondiendo a esa necesidad y enseña a la vez el resultado constructivo más fuerte.
Qué puede hacer con ella
Ecuaciones diofánticas lineales
Obtenga una solución particular (x, y) para a*x + b*y = mcd, luego escale y parametrice al resolver a*x + b*y = c en concursos o tareas.
Bloque base del inverso modular
Cuando mcd(a, m) = 1, reduzca el coeficiente de Bézout de a módulo m para recuperar un inverso modular en ejercicios de criptografía y teoría de números.
Preguntas frecuentes
¿Qué es el algoritmo de Euclides extendido?
Calcula mcd(a, b) y enteros x, y (coeficientes de Bézout) tales que a*x + b*y iguala ese mcd, rastreando combinaciones lineales en los pasos de resto euclídeo.
¿Son únicos los coeficientes?
No. Si (x, y) funciona, también (x + k*(b/g), y − k*(a/g)) para cualquier entero k. Esta herramienta devuelve una solución particular del algoritmo iterativo.
¿Qué rango de enteros se admite?
Cada uno de a y b debe ser un entero con valor absoluto como máximo 9007199254740991 (Number.MAX_SAFE_INTEGER).
¿Cuánto cuesta?
La herramienta del navegador es gratis y se ejecuta en local.
¿Cómo hallo los coeficientes de Bézout de 240 y 46?
Escriba los dos números. El máximo común divisor es 2 y los coeficientes son −9 y 47, porque 240 × (−9) + 46 × 47 = 2. El resultado incluye esa igualdad para que pueda comprobarla.
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/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", 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": 240,
"b": 46
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"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
Esta capacidad toma dos enteros, rechaza el caso indefinido en que ambos son cero y devuelve un JSON estable con mcd, x, y, una verificación y una cadena de ecuación legible que puede pegar en notas o pruebas.
Qué envía usted y qué recibe
Proporcione enteros a y b (se aceptan los alias first o m para a, y second o n para b). No enteros, campos vacíos y valores fuera del máximo absoluto de enteros seguros de la plataforma se rechazan con invalid_input y no se cobran.
Dónde aparecen los coeficientes de Bézout en la práctica
Como la capacidad es un motor de parse puro, no hay deriva de modelo, ni dependencia de red, ni estado almacenado: el mismo par siempre produce el mismo JSON para una convención fija de coeficientes. El precio de la API es la base publicada de $0.002 por ítem exitoso; la validación fallida no consume saldo.
Casos de integración
Docencia y comprobaciones automatizadas
Muestre a los estudiantes la identidad a*x + b*y = mcd con un campo de ecuación JSON estable, y conecte el mismo contrato a correctores o fixtures de CI.
Preguntas técnicas
¿Por qué se rechazan a y b ambos cero?
mcd(0, 0) es indefinido. No hay un máximo común divisor positivo, así que la API devuelve invalid_input y no cobra.