Contar raízes primitivas módulo n
Módulo 18 existem exatamente 2 raízes primitivas, o resultado de aplicar duas vezes o totiente de Euler. Digite um módulo e veja quantos geradores ele tem, ou um aviso claro quando não tem nenhum, como acontece com o 8. 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
- 18
- Módulo
- 18
- Quantidade de raízes primitivas
- 2
Este contador verifica se um módulo admite raízes primitivas e, quando admite, retorna a quantidade exata. O resultado é o totiente de Euler do totiente de Euler do módulo, escrito como phi(phi(n)). A calculadora abrange toda a família de módulos elegíveis, sem presumir que a entrada seja prima. Se o módulo pertencer a uma classe sem raízes primitivas, ela informa um erro claro de entrada em vez de retornar um zero enganoso.
O que a contagem representa
Uma raiz primitiva módulo n é uma classe de resíduos cujas potências sucessivas geram todas as classes invertíveis módulo n. Na linguagem de grupos, ela é um gerador do grupo multiplicativo dos inteiros módulo n. Esta ferramenta responde a uma pergunta precisa: quantas classes de resíduos distintas geram esse grupo?
Ela não lista os geradores nem procura o menor deles. Quando existe uma raiz primitiva, o grupo multiplicativo é cíclico e possui phi(n) elementos. Um grupo cíclico de ordem phi(n) tem exatamente phi(phi(n)) geradores, valor retornado aqui.
Por exemplo, módulo 18, os resíduos invertíveis formam um grupo cíclico de ordem 6, e phi(6) é 2; portanto, existem duas raízes primitivas. A contagem trata de classes módulo n, não de representantes inteiros arbitrários: valores separados por um múltiplo de n descrevem a mesma raiz. Essa distinção torna o resultado útil em provas, exercícios e algoritmos nos quais o tamanho do conjunto gerador importa mais que a identidade de cada elemento.
Quais módulos possuem raízes primitivas
Raízes primitivas não existem para todo módulo positivo. A classificação completa afirma que elas existem somente quando n é 2, 4, uma potência p^k de primo ímpar ou o dobro de uma potência de primo ímpar, 2p^k. A calculadora fatora o módulo informado e aplica esse teorema antes de calcular a quantidade.
Isso é essencial porque avaliar phi(phi(n)) para um módulo inelegível produz um número positivo mesmo quando não há geradores. Por exemplo, phi(8) é 4 e phi(4) é 2, mas não existe raiz primitiva módulo 8; retornar 2 seria matematicamente incorreto. Por isso, esta capacidade rejeita tal módulo com um erro explícito.
Módulos primos maiores que dois entram como o caso especial p^1, enquanto exemplos compostos como 9, 14, 18 e 25 também são aceitos. Já 8, 12, 15 e 20 não são. A verificação da classificação fica separada da fórmula de contagem para que a saída sempre represente um conjunto real de raízes primitivas.
Como usar e interpretar o resultado
Envie um inteiro n entre 2 e 1,000,000,000,000. A entrada deve ser um inteiro numérico, e não uma string decimal, fração, aproximação científica, valor negativo ou inteiro inseguro do JavaScript. O limite superior mantém a fatoração finita e previsível, cobrindo ainda uma faixa ampla de cálculos acadêmicos e práticos.
Internamente, o algoritmo usa divisão por tentativa determinística para obter a estrutura de potências primas, aplica o teorema de existência, calcula phi(n) pelos fatores primos distintos e então calcula phi(phi(n)). Nenhuma solicitação de rede ou busca aleatória é feita, portanto entradas iguais sempre geram saídas iguais.
Casos de uso
Conferir um exercício de teoria dos números
Verifique a quantidade esperada de geradores antes de enumerar manualmente as raízes primitivas.
Dimensionar uma busca de geradores
Descubra quantas classes de resíduos válidas uma busca exaustiva de raízes primitivas deve encontrar.
Validar um módulo elegível
Rejeite um módulo cujo grupo multiplicativo não seja cíclico antes que outro algoritmo pressuponha uma raiz primitiva.
Perguntas frequentes
Qual fórmula a calculadora usa?
Para um módulo que admite raízes primitivas, ela retorna phi(phi(n)), em que phi é o totiente de Euler.
Por que a ferramenta retorna um erro em vez de zero?
O contrato diferencia um caso matemático inelegível de uma contagem válida. Por isso, um módulo sem raízes primitivas é informado como entrada inválida.
Quais módulos admitem raízes primitivas?
Exatamente 2, 4, as potências p^k de um primo ímpar e o dobro dessas potências, 2p^k.
A ferramenta lista as raízes primitivas?
Não. Ela retorna apenas quantas classes de resíduos são raízes primitivas módulo n.
Módulos primos são aceitos?
Sim. Todo módulo primo possui raízes primitivas, inclusive 2; primos ímpares são casos de potências de primo ímpar.
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/count-primitive-roots \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":18}'const res = await fetch("https://api.kit.forhosting.com/numth/count-primitive-roots", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 18
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/count-primitive-roots",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 18
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/count-primitive-roots", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":18}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":18}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/count-primitive-roots", 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": 18
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.count_primitive_roots",
"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
Como usar e interpretar o resultado
A resposta repete esse valor em modulus e fornece o inteiro exato em primitive_root_count. Interprete uma resposta invalid_input que diga não existirem raízes primitivas como uma conclusão matemática sobre o módulo, não como falha temporária. Se você precisar das próprias raízes, use uma ferramenta de busca ou enumeração; este endpoint retorna intencionalmente apenas a cardinalidade. Cada solicitação API custa US$ 0,002, sempre com a mesma aritmética exata.
Perguntas técnicas
Quanto custa uma solicitação API?
Cada solicitação API custa US$ 0,002.