Teorema de Lucas
Obtenha C(n, k) módulo um primo sem fatoriais enormes: C(1000, 200) módulo 7 vale 1, escrevendo os dois números na base 7 e multiplicando pequenos binomiais dos dígitos. Os dígitos aparecem para você conferir cada passo. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- N
- 1.000
- K
- 200
- Potência (W)
- 7
- Resultado
- 1
- Dígitos de n
- 6, 2, 6, 2
- Dígitos de k
- 4, 0, 4, 0
O teorema de Lucas é o caminho clássico para avaliar um coeficiente binomial módulo um primo quando n é grande o bastante para tornar o fatorial de n impraticável. O produto é exatamente C(n, k) mod p; se algum dígito inferior superar o superior correspondente, o valor inteiro é zero. Programação competitiva, teoria dos números combinatória e exercícios de criptografia precisam dessa redução quando fatoriais diretos estouram ou custam demais.
O que o teorema de Lucas afirma e quando voce precisa dele
Na combinatória elementar o coeficiente binomial C(n, k) conta os subconjuntos de k elementos de um conjunto com n e equivale ao fatorial de n dividido pelo fatorial de k vezes o fatorial de (n menos k). Essa forma fechada deixa de servir assim que n passa de alguns milhares se voce só precisa da resposta módulo um primo pequeno: os fatoriais intermediários explodem e as aproximações em ponto flutuante perdem o resíduo exato. O teorema de Lucas, nomeado em homenagem a Édouard Lucas, resolve exatamente esse problema modular.
Cada fator usa argumentos menores que p, de modo que se calcula com um laço multiplicativo curto e inversos modulares que existem porque p é primo e todo denominador é menor que p. Só esse teste responde a muitas perguntas do tipo «o binomial é divisível por este primo?» sem calcular um produto completo.
O teorema exige que p seja primo; para módulos compostos o mesmo produto de dígitos não é válido em geral, e esta capacidade recusa deliberadamente um p não primo em vez de devolver um resíduo errado em silêncio. Estudantes que encontram o teorema em material de olimpíadas, desenvolvedores que integram bibliotecas de programação competitiva e instrutores que preparam laboratórios de aritmética modular se beneficiam de uma única função determinística que impõe a hipótese de primalidade e expõe as expansões de dígitos usadas na demonstração.
Como esta calculadora aplica o teorema de Lucas passo a passo
Chame a capacidade com os campos inteiros n, k e p. Tanto n quanto k devem ser inteiros não negativos de no máximo um trilhão; p deve ser um primo entre dois e um milhão e três inclusive. A implementação valida primeiro tipos e limites e depois executa um teste de primalidade por divisão de tentativa determinístico sobre p.
Quando p é aceito, o solucionador percorre os dígitos na base p de n e k do menos significativo ao mais significativo. Cada binomial pequeno usa a fórmula multiplicativa com inversos modulares via o pequeno teorema de Fermat (a elevado a p menos dois módulo p), implementado com produtos intermediários exatos em BigInt para não perder precisão dentro dos limites publicados.
Os casos de borda são estáveis e documentados: quando k é zero ou igual a n o resultado é um módulo p (ou zero só se p valer um, o que é rejeitado); quando k supera n o resultado é zero; quando n e k são ambos zero os arrays de dígitos são o único dígito zero e o resultado é um módulo p.
Casos de uso
Programação competitiva e prática de olimpíadas
Programadores competitivos podem verificar C(n, k) mod p para n grandes frente a casos de exemplo e ver um erro explícito quando um módulo resulta composto por acidente.
Laboratórios de teoria dos números e combinatória
Instrutores e estudantes podem inspecionar os dígitos na base p junto ao produto modular enquanto aprendem o teorema de Lucas e o teste de zero por divisibilidade prima.
Perguntas frequentes
O que acontece se p não for primo?
A mensagem indica que p deve ser um primo (por exemplo quando p é composto ou igual a 1). A validação falha não é cobrada.
Qual algoritmo calcula o binomial modular?
Binomiais de dígito pequeno usam a fórmula multiplicativa com inversos modulares.
A calculadora do teorema de Lucas é gratuita?
A ferramenta do navegador roda grátis no seu dispositivo.
Quais faixas de n, k e p são aceitas?
n e k devem ser inteiros não negativos de no máximo 1,000,000,000,000. p deve ser um primo de 2 a 1,000,003. Valores fora desses limites, ou p composto, são rejeitados.
Como sei se C(n, k) é divisível por um primo?
Escreva n e k na base p e compare dígito a dígito. Se algum dígito de k for maior que o dígito correspondente de n, o resultado é 0, ou seja, p divide o coeficiente binomial.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
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)Exemplo de requisição
{
"n": 1000,
"k": 200,
"p": 7
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_theorem_binomial",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Dados inteiros não negativos n e k e um módulo primo p, o teorema escreve n e k na base p e multiplica os binomiais de dígitos C(n_i, k_i) módulo p. Esta calculadora aceita n, k e p, rejeita módulos compostos com um erro invalid_input claro, executa um percurso de Lucas determinístico e devolve o resultado modular junto com os dígitos na base p para que voce possa auditar cada passo sem rederivar a expansão à mão.
O que o teorema de Lucas afirma e quando voce precisa dele
Escreva n e k na base p como sequências de dígitos n_i e k_i, cada dígito estritamente menor que p. Então C(n, k) é congruente módulo p ao produto sobre i de C(n_i, k_i). Um corolário crucial é o teste de zero: se em alguma posição o dígito inferior k_i for maior que n_i, aquele binomial de dígito é zero e portanto C(n, k) é divisível por p.
Como esta calculadora aplica o teorema de Lucas passo a passo
Valores compostos, um, zero e negativos falham com invalid_input e uma mensagem que nomeia p; essas falhas não são cobradas. Para cada par (n_i, k_i) ou encurta para zero se k_i superar n_i, ou multiplica o produto acumulado por C(n_i, k_i) mod p. A resposta devolve n, k, p, result (o resíduo de zero a p menos um), is_zero, os arrays n_digits e k_digits na ordem do dígito menos significativo primeiro, e method com a string lucas.
Uso prático, limites, preço e entrega
Use a ferramenta do navegador quando quiser uma verificação rápida de Lucas ao ler uma nota de teoria dos números, validar um exemplo de concurso ou depurar uma rotina de combinatória modular. As entradas aceitas são inteiros não negativos n e k até um trilhão e primos p de dois a um milhão e três. Se voce precisar do C(n, k) inteiro sem restrição, de uma linha binomial para todo k, ou de binomiais modulares para módulos compostos via teorema chinês do resto, use uma capacidade dedicada; esta ferramenta para deliberadamente em Lucas para um primo p verificado, de modo que o contrato permanece simples e auditável. Use a API quando um avaliador, uma plataforma de ensino ou um script precisar de muitas avaliações de C(n, k) mod p sem embutir um portão de primalidade e um percurso de dígitos. Cada requisição bem-sucedida é um item faturável a US$ 0,002; falhas de validação e módulos não primos não consomem saldo. Os resultados são determinísticos: o mesmo triplo sempre produz o mesmo resíduo, os mesmos arrays de dígitos e o mesmo indicador is_zero. Conecte o endpoint a ajudas de olimpíadas, sandboxes de programação competitiva, demos didáticas de criptografia que toquem coeficientes binomiais módulo primos pequenos, ou qualquer pipeline de inteiros que prefira aritmética modular exata a bibliotecas aproximadas. Como a unidade é um único item e o motor é parse puro, a latência permanece baixa e o canal web gratuito espelha a API paga sem um segundo caminho de código que pudesse divergir.
Casos de integração
Avaliadores de deveres e pipelines modulares
Avaliadores automáticos e scripts podem confirmar resíduos, detectar p não primo via invalid_input e manter cada produto intermediário dentro dos limites documentados.
Perguntas técnicas
Como calculo C(n,k) mod p com esta API?
Envie JSON com os campos inteiros n, k e p (p primo) para numth.lucas_theorem_binomial. Em caso de sucesso a resposta devolve result em 0..p−1, is_zero, arrays de dígitos na base p e method "lucas".