Teorema de Lucas
Obtenga C(n, k) módulo un primo sin factoriales enormes: C(1000, 200) módulo 7 vale 1, al escribir ambos números en base 7 y multiplicar binomiales pequeños de sus dígitos. Se muestran los dígitos para que revise cada paso. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- N
- 1 000
- K
- 200
- Potencia (W)
- 7
- Resultado
- 1
- Dígitos de n
- 6, 2, 6, 2
- Dígitos de k
- 4, 0, 4, 0
El teorema de Lucas es la vía clásica para evaluar un coeficiente binomial módulo un número primo cuando n es tan grande que el factorial de n resulta inviable. El producto es exactamente C(n, k) mod p; si algún dígito inferior supera al superior correspondiente, el valor completo es cero. La programación de concursos, la teoría de números combinatoria y los ejercicios de criptografía necesitan esta reducción cuando los factoriales directos desbordan o cuestan demasiado.
Qué afirma el teorema de Lucas y cuándo lo necesita
En combinatoria elemental el coeficiente binomial C(n, k) cuenta los subconjuntos de k elementos de un conjunto de n y equivale al factorial de n dividido por el factorial de k por el factorial de (n menos k). Esa forma cerrada deja de servir en cuanto n supera unos pocos miles si solo necesita la respuesta módulo un primo pequeño: los factoriales intermedios explotan y las aproximaciones en coma flotante pierden el residuo exacto. El teorema de Lucas, llamado así por Édouard Lucas, resuelve justo este problema modular.
Cada factor usa argumentos menores que p, de modo que se calcula con un bucle multiplicativo corto e inversos modulares que existen porque p es primo y todo denominador es menor que p. Solo esa prueba responde a muchas preguntas del tipo «¿es el binomial divisible por este primo?» sin calcular un producto completo.
El teorema exige que p sea primo; para módulos compuestos el mismo producto de dígitos no es válido en general, y esta capacidad rechaza deliberadamente un p no primo en lugar de devolver un residuo incorrecto en silencio. Estudiantes que encuentran el teorema en material de olimpiadas, desarrolladores que integran bibliotecas de programación competitiva e instructores que preparan laboratorios de aritmética modular se benefician de una sola función determinista que impone la hipótesis de primalidad y expone las expansiones de dígitos usadas en la demostración.
Cómo aplica esta calculadora el teorema de Lucas paso a paso
Invoque la capacidad con los campos enteros n, k y p. Tanto n como k deben ser enteros no negativos de a lo sumo un billón (10^12); p debe ser un primo entre dos y un millón tres inclusive. La implementación valida primero tipos y cotas y después ejecuta una prueba de primalidad por división de prueba determinista sobre p.
Cuando p se acepta, el solucionador recorre los dígitos en base p de n y k desde el menos significativo al más significativo. Cada binomial pequeño usa la fórmula multiplicativa con inversos modulares vía el pequeño teorema de Fermat (a elevado a p menos dos módulo p), implementado con productos intermedios exactos en BigInt para no perder precisión dentro de las cotas publicadas.
Los casos límite son estables y están documentados: cuando k es cero o igual a n el resultado es uno módulo p (o cero solo si p vale uno, que se rechaza); cuando k supera n el resultado es cero; cuando n y k son ambos cero los arrays de dígitos son el dígito cero único y el resultado es uno módulo p.
Qué puede hacer con ella
Programación de concursos y práctica de olimpiadas
Los programadores competitivos pueden verificar C(n, k) mod p para n grandes frente a casos de ejemplo y ver un error explícito cuando un módulo resulta compuesto por accidente.
Laboratorios de teoría de números y combinatoria
Instructores y estudiantes pueden inspeccionar los dígitos en base p junto al producto modular mientras aprenden el teorema de Lucas y la prueba de cero por divisibilidad prima.
Preguntas frecuentes
¿Qué ocurre si p no es primo?
El mensaje indica que p debe ser un primo (por ejemplo cuando p es compuesto o igual a 1). La validación fallida no se cobra.
¿Qué algoritmo calcula el binomial modular?
Los binomiales de dígito pequeño usan la fórmula multiplicativa con inversos modulares.
¿Es gratuita la calculadora del teorema de Lucas?
La herramienta del navegador se ejecuta gratis en su dispositivo.
¿Qué rangos de n, k y p se aceptan?
n y k deben ser enteros no negativos de a lo sumo 1,000,000,000,000. p debe ser un primo de 2 a 1,000,003. Los valores fuera de esos límites, o un p compuesto, se rechazan.
¿Cómo sé si C(n, k) es divisible por un primo?
Escriba n y k en base p y compárelos dígito a dígito. Si algún dígito de k es mayor que el dígito correspondiente de n, el resultado es 0, lo que significa que p divide al coeficiente binomial.
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/lucas-theorem-binomial \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":1000,"k":200,"p":7}'const res = await fetch("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 1000,
"k": 200,
"p": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/lucas-theorem-binomial",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 1000,
"k": 200,
"p": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":1000,"k":200,"p":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":1000,"k":200,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-theorem-binomial", 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
{
"n": 1000,
"k": 200,
"p": 7
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_theorem_binomial",
"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.
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
Dados enteros no negativos n y k y un módulo primo p, el teorema escribe n y k en base p y multiplica los binomiales de dígitos C(n_i, k_i) módulo p. Esta calculadora acepta n, k y p, rechaza módulos compuestos con un error invalid_input claro, ejecuta un recorrido de Lucas determinista y devuelve el resultado modular junto con los dígitos en base p para que usted pueda auditar cada paso sin rederivar la expansión a mano.
Qué afirma el teorema de Lucas y cuándo lo necesita
Escriba n y k en base p como secuencias de dígitos n_i y k_i, cada dígito estrictamente menor que p. Entonces C(n, k) es congruente módulo p al producto sobre i de C(n_i, k_i). Un corolario crucial es la prueba de cero: si en alguna posición el dígito inferior k_i es mayor que n_i, ese binomial de dígito es cero y por tanto C(n, k) es divisible por p.
Cómo aplica esta calculadora el teorema de Lucas paso a paso
Valores compuestos, uno, cero y negativos fallan con invalid_input y un mensaje que nombra p; esos fallos no se cobran. Para cada par (n_i, k_i) o bien corta a cero si k_i supera n_i, o multiplica el producto acumulado por C(n_i, k_i) mod p. La respuesta devuelve n, k, p, result (el residuo de cero a p menos uno), is_zero, los arrays n_digits y k_digits en orden del dígito menos significativo primero, y method con la cadena lucas.
Uso práctico, límites, precio y entrega
Use la herramienta del navegador cuando desee una comprobación rápida de Lucas al leer una nota de teoría de números, verificar un ejemplo de concurso o depurar una rutina de combinatoria modular. Las entradas aceptadas son enteros no negativos n y k hasta un billón y primos p de dos a un millón tres. Si necesita el C(n, k) entero sin restricción, una fila binomial para todo k, o binomiales modulares para módulos compuestos vía el teorema chino del resto, use una capacidad dedicada; esta herramienta se detiene deliberadamente en Lucas para un primo p verificado, de modo que el contrato permanece simple y auditable. Use la API cuando un calificador, una plataforma docente o un script necesite muchas evaluaciones de C(n, k) mod p sin incrustar una puerta de primalidad y un recorrido de dígitos. Cada petición exitosa es un ítem facturable a $0.002; los fallos de validación y los módulos no primos no consumen saldo. Los resultados son deterministas: el mismo triple siempre produce el mismo residuo, los mismos arrays de dígitos y el mismo indicador is_zero. Conecte el endpoint a ayudas de olimpiadas, sandboxes de programación competitiva, demos docentes de criptografía que toquen coeficientes binomiales módulo primos pequeños, o cualquier pipeline de enteros que prefiera aritmética modular exacta frente a bibliotecas aproximadas. Como la unidad es un solo ítem y el motor es parse puro, la latencia se mantiene baja y el canal web gratuito refleja la API de pago sin un segundo camino de código que pudiera divergir.
Casos de integración
Calificadores de deberes y pipelines modulares
Los calificadores automáticos y los scripts pueden confirmar residuos, detectar p no primo mediante invalid_input y mantener cada producto intermedio dentro de las cotas documentadas.
Preguntas técnicas
¿Cómo calculo C(n,k) mod p con esta API?
Envíe JSON con los campos enteros n, k y p (p primo) a numth.lucas_theorem_binomial. Si tiene éxito, la respuesta devuelve result en 0..p−1, is_zero, arrays de dígitos en base p y method "lucas".