Todas as raízes primitivas módulo n
Módulo 14 há 6 resíduos invertíveis e exatamente duas raízes primitivas, 3 e 5. Informe um módulo de 2 a 10.000 e receba a lista completa e ordenada de geradores, a phi de Euler e a contagem. 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
- 14
- Phi
- 6
- Quantidade
- 2
- Raízes primitivas
- 3, 5
Esta calculadora de todas as raízes primitivas módulo n retorna o conjunto completo e ordenado de geradores do grupo multiplicativo de unidades módulo um inteiro n. Primeiro, ela determina se o módulo pertence a uma família que admite raízes primitivas; depois calcula o totiente de Euler, encontra um gerador e deriva todos os demais. A resposta inclui o módulo, o totiente, a quantidade e a lista completa de raízes. Valores abaixo de dois e módulos sem raízes primitivas geram um erro claro.
O que significa a lista completa de raízes primitivas
Uma raiz primitiva módulo n é um resíduo cujas potências repetidas geram todas as classes de resíduos invertíveis módulo n. A palavra essencial é todas: um número pode ser coprimo com n e ainda percorrer apenas um subgrupo próprio, portanto ser uma unidade é necessário, mas não suficiente. A capacidade retorna todos os representantes positivos entre 1 e n menos 1 com ordem multiplicativa exatamente igual a phi(n).
Para o módulo 14, por exemplo, o grupo de unidades tem seis elementos e o conjunto completo de geradores contém dois resíduos. A contagem permite conferir o resultado: quando existem raízes primitivas, há phi(phi(n)) delas. O módulo especial 2 possui corretamente a única raiz 1.
Um módulo sem gerador para todo o grupo é rejeitado; uma lista vazia esconderia que o grupo não é cíclico.
Como a existência e cada gerador são verificados
Nem todo módulo admite raízes primitivas. O teorema de classificação afirma que o grupo multiplicativo módulo n é cíclico exatamente quando n é 2, 4, uma potência de primo ímpar ou duas vezes uma potência de primo ímpar. A calculadora fatora n e verifica essa condição estrutural antes da busca.
Para um módulo admissível, calcula phi(n), fatora a ordem do grupo e testa unidades candidatas com exponenciação modular. Um candidato g tem ordem completa phi(n) se, para cada divisor primo distinto q de phi(n), g elevado a phi(n) dividido por q não for congruente a 1 módulo n. Depois de encontrar g, todas as raízes são potências g elevado a k em que k é coprimo com phi(n).
A implementação enumera esses expoentes, calcula resíduos exatos e ordena o resultado. Ela não usa aleatoriedade, tabelas externas, rede nem horário atual; a mesma entrada sempre produz o mesmo conteúdo numérico.
Como usar o resultado em matemática e software
Listas completas de geradores são úteis quando um problema pede mais do que a menor raiz primitiva. Estudantes podem comparar os resíduos retornados com tabelas de potências feitas à mão e entender por que a quantidade de geradores é phi(phi(n)). Docentes podem preparar gabaritos que incluam todas as respostas válidas.
Desenvolvedores podem criar dados de teste para rotinas de ordem multiplicativa, verificar código de enumeração ou escolher entre vários geradores conforme outra regra da aplicação. Os erros também são instrutivos: testar os módulos 8 ou 15 mostra que muitos compostos conhecidos têm grupos de unidades não cíclicos, embora contenham vários resíduos invertíveis. Informe n como inteiro ou cadeia decimal simples.
Casos de uso
Conferir um exercício de teoria dos números
Compare um cálculo manual com o conjunto completo e ordenado de geradores módulo n.
Gerar dados de teste determinísticos
Crie valores esperados exatos para código que calcula ordens multiplicativas ou grupos cíclicos de unidades.
Ensinar grupos de unidades cíclicos e não cíclicos
Compare módulos admissíveis com valores que não podem ter raiz primitiva e explique o teorema de classificação.
Perguntas frequentes
Quais módulos têm raízes primitivas?
Exatamente 2, 4, potências de primos ímpares e duas vezes essas potências. Os demais são rejeitados porque seus grupos de unidades não são cíclicos.
Por que um resíduo coprimo pode não ser uma raiz primitiva?
A coprimalidade apenas torna o resíduo uma unidade. Uma raiz primitiva também precisa ter a maior ordem multiplicativa possível, phi(n).
Quantas raízes primitivas o resultado deve conter?
Quando elas existem, sua quantidade é phi(phi(n)). A resposta inclui a contagem calculada junto ao array.
Por que n é limitado a 10,000?
A saída lista todos os geradores e, portanto, cresce com n. O limite mantém previsíveis o cálculo exaustivo e o tamanho da resposta.
Como sei se um número é raiz primitiva módulo n?
As suas potências precisam percorrer todos os resíduos coprimos com n antes de voltar a 1, ou seja, a sua ordem deve ser igual a phi(n). Módulo 14, as potências de 3 alcançam os seis resíduos, então 3 é raiz primitiva.
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/all-primitive-roots \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":14}'const res = await fetch("https://api.kit.forhosting.com/numth/all-primitive-roots", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 14
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/all-primitive-roots",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 14
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/all-primitive-roots", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":14}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":14}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/all-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": 14
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.all_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.
Limites
max_n | 10000 |
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
A mesma aritmética determinística permite verificações rápidas e automação reproduzível via API por US$ 0,002 em cada solicitação bem-sucedida.
O que significa a lista completa de raízes primitivas
A resposta informa n, o totiente de Euler phi, a quantidade de raízes primitivas e o array primitive_roots em ordem numérica.
Como usar o resultado em matemática e software
A entrada é limitada a 10,000 porque a resposta solicitada é exaustiva e pode conter muitas raízes; o limite mantém previsíveis a renderização, o tamanho da API e o tempo de execução. Solicitações bem-sucedidas custam US$ 0,002; entradas incompatíveis ou malformadas são identificadas claramente.
Perguntas técnicas
Quanto custa uma solicitação de API?
Uma solicitação bem-sucedida de API custa US$ 0,002. Uma entrada inválida retorna um erro, não uma lista de raízes.