Calculadora de Raízes Primitivas

Use esta Calculadora de Raízes Primitivas para informar valores, ajustar opções e analisar os resultados em um espaço de trabalho compacto e responsivo.

Os resultados são calculados automaticamente à medida que você informa os dados.

Módulo n Candidato g (opcional) Listar raízes quando n <=

Mostrar potências geradas

Teste de ordem e fatoração de phi

Resultado Informe um módulo.

Aviso: Todas as ferramentas deste site destinam-se apenas a fins educacionais e informativos. As entradas aceitas produzem resultados inteiros exatos; isto não constitui aconselhamento profissional. Verifique definições, premissas e método antes de confiar nos resultados. Consulte nossos Termos de Uso.

Premissas e limitações

Esta Calculadora de Raízes Primitivas é destinada a fins educacionais e informativos. Entradas aceitas produzem resultados inteiros exatos com base nas definições e métodos apresentados na página. Isto não constitui aconselhamento profissional, e resultados importantes devem ser verificados de forma independente antes de embasar decisões. Para usos profissionais, sensíveis à segurança, de construção, engenharia, oficiais ou de alto custo, confirme os resultados com um método apropriado, normas vigentes, tolerâncias necessárias e um profissional qualificado. O uso desta calculadora está sujeito aos nossos Termos de Uso.

▼ Veja explicações e dicas abaixo ▼

Calculadoras relacionadas

O que é uma raiz primitiva?

Uma raiz primitiva é um número cujas potências geram todos os resíduos invertíveis para um módulo escolhido. Na aritmética modular, o módulo $n$ define o ciclo dos restos. Somente números coprimos de $n$ são invertíveis módulo $n$, e esses resíduos invertíveis são chamados de unidades módulo $n$.

Um número $g$ é uma raiz primitiva módulo $n$ quando as potências de $g$ produzem todas as unidades módulo $n$ antes de a sequência retornar a $1$. Na linguagem de grupos, $g$ é um gerador do grupo multiplicativo das unidades módulo $n$.

Por exemplo, módulo $7$, as unidades são $1,2,3,4,5,6$. As potências de $3$ dão

$$ 3^0,3^1,3^2,3^3,3^4,3^5,3^6 \pmod{7} = 1,3,2,6,4,5,1. $$

A sequência alcança todos os resíduos não nulos módulo $7$ antes de retornar a $1$, portanto $3$ é uma raiz primitiva módulo $7$.

As raízes primitivas não existem para todos os módulos. Para $n \ge 2$, as raízes primitivas existem exatamente quando

$$ n = 2, \quad n = 4, \quad n = p^k, \quad \text{or} \quad n = 2p^k, $$

onde $p$ é um primo ímpar e $k \ge 1$.

Quando o candidato fica em branco, a calculadora encontra um gerador módulo $p$, verifica se ele pode ser elevado diretamente a $p^2$, ajusta-o em $p$ quando necessário e escolhe o representante ímpar para $2p^k$. Em seguida, verifica-se de forma independente se o valor construído tem ordem $\varphi(n)$.

Por que as raízes primitivas são importantes

As raízes primitivas conectam várias ideias fundamentais da teoria dos números: aritmética modular, máximo divisor comum, função totiente de Euler, grupos cíclicos e exponenciação modular. Elas ajudam a responder a uma pergunta prática: um único valor inicial pode gerar todos os resíduos invertíveis módulo $n$ por meio de multiplicações repetidas?

Isportanto é importante em vários contextos:

Estudantes usam raízes primitivas para entender como a multiplicação modular se comporta.
Quem estuda teoria dos números usa-as para estudar grupos cíclicos e sistemas reduzidos de resíduos.
Programadores de competições usam testes relacionados ao trabalhar com aritmética modular, geradores e módulos primos.
Quem estuda criptografia encontra ideias semelhantes sobre geradores ao estudar logaritmos discretos e exemplos de troca de chaves.

As raízes primitivas são úteis para aprendizado e experimentação, mas a escolha de parâmetros para sistemas criptográficos reais exige normas especializadas e revisão de especialistas.

Termos importantes

Módulo: O número $n$ usado para definir restos na aritmética modular.
Resíduo: Uma classe de restos módulo $n$. Por exemplo, $20 \equiv 2 \pmod{18}$.
Coprimos: Dois inteiros são coprimos quando seu máximo divisor comum é $1$.
Unidade módulo $n$: Um resíduo coprimo de $n$ e, portanto, possui um inverportanto multiplicativo módulo $n$.
Sistema reduzido de resíduos: O conjunto completo de resíduos módulo $n$ que são coprimos de $n$.
Função totiente de Euler: $\varphi(n)$, o número de unidades módulo $n$.
Ordem multiplicativa: O menor expoente positivo $d$ tal que $g^d \equiv 1 \pmod{n}$, supondo que $g$ seja uma unidade módulo $n$.
Gerador: Um elemento cujas potências produzem todos os elementos de um grupo. Uma raiz primitiva é um gerador do grupo de unidades módulo $n$.

Como as raízes primitivas funcionam

As raízes primitivas se baseiam em três ideias relacionadas: quais resíduos são unidades, quantas unidades existem e qual é a duração de um ciclo de potências.

Primeiro, um candidato $g$ deve ser uma unidade módulo $n$. Isportanto significa que

$$ \gcd(g,n)=1. $$

Se $g$ não for coprimo de $n$, ele não pode ser uma raiz primitiva, pois suas potências não conseguem percorrer o conjunto completo de resíduos invertíveis.

Segundo, o tamanho do conjunto de unidades é $\varphi(n)$. Se

$$ n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, $$

então a função totiente de Euler pode ser calculada como

$$ \varphi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right). $$

De forma equivalente,

$$ \varphi(n)=\prod_{i=1}^{r}p_i^{e_i-1}(p_i-1). $$

Terceiro, a ordem multiplicativa de $g$ módulo $n$ é a duração do ciclo de potências antes de retornar a $1$:

$$ \operatorname{ord}_n(g)=\min\{d\ge 1: g^d\equiv 1\pmod{n}\}. $$

Uma unidade $g$ é uma raiz primitiva exatamente quando

$$ \operatorname{ord}_n(g)=\varphi(n). $$

Isportanto significa que o ciclo é o mais longo possível: ele visita cada unidade exatamente uma vez antes de se repetir.

O teste dos divisores primos

Uma forma direta de testar um candidato é fatorar $\varphi(n)$ e verificar os divisores primos de $\varphi(n)$ . Se $g$ seja uma unidade módulo $n$, então $g$ é primitivo quando

$$ g^{\varphi(n)/q}\not\equiv 1\pmod{n} $$

para todo divisor primo $q$ de $\varphi(n)$.

Isportanto funciona porque a ordem de qualquer unidade divide $\varphi(n)$ . Se a ordem for um divisor próprio de $\varphi(n)$, pelo menos uma dessas verificações com expoente reduzido retornará $1$, mostrando que o ciclo do candidato é curto demais.

Exemplos práticos de raízes primitivas

Exemplo 1: um módulo primo

Seja $n=7$ e teste $g=3$.

Como $7$ é primo,

$$ \varphi(7)=6. $$

As potências de $3$ módulo $7$ are

$$ \begin{aligned} 3^0 &\equiv 1 \pmod{7},\\ 3^1 &\equiv 3 \pmod{7},\\ 3^2 &\equiv 2 \pmod{7},\\ 3^3 &\equiv 6 \pmod{7},\\ 3^4 &\equiv 4 \pmod{7},\\ 3^5 &\equiv 5 \pmod{7},\\ 3^6 &\equiv 1 \pmod{7}. \end{aligned} $$

Os resíduos $1,3,2,6,4,5$ são todas as seis unidades módulo $7$. Portanto,

$$ \operatorname{ord}_7(3)=6=\varphi(7), $$

portanto $3$ é uma raiz primitiva módulo $7$.

Exemplo 2: um módulo composto com raízes primitivas

Seja $n=18$ e teste $g=5$.

A fatoração em primos é

$$ 18=2\cdot 3^2, $$

$$ \varphi(18)=18\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=6. $$

As unidades módulo $18$ are

$$ 1,5,7,11,13,17. $$

As potências de $5$ módulo $18$ are

$$ 5^0,5^1,5^2,5^3,5^4,5^5,5^6 \pmod{18} =1,5,7,17,13,11,1. $$

O ciclo alcança todas as seis unidades antes de retornar a $1$, so

$$ \operatorname{ord}_{18}(5)=6=\varphi(18). $$

Assim, $5$ é uma raiz primitiva módulo $18$.

Exemplo 3: um módulo sem raízes primitivas

Seja $n=8$. As unidades módulo $8$ are

$$ 1,3,5,7, $$

portanto $\varphi(8)=4$. Tente $g=3$:

$$ 3^1\equiv 3\pmod{8}, \qquad 3^2=9\equiv 1\pmod{8}. $$

A ordem de $3$ módulo $8$ é $2$, e não $4$. Ciclos curtos semelhantes ocorrem para as outras unidades. Além disso, $8$ não está em uma das formas $2$, $4$, $p^k$, ou $2p^k$ com $p$ um primo ímpar; portanto, não existem raízes primitivas módulo $8$.

Como interpretar o resultado

Um resultado sobre raízes primitivas tem duas partes distintas: o estado do módulo e o estado do candidato.

Existem raízes primitivas informa se o módulo $n$ está em uma das formas permitidas. Isportanto depende apenas de $n$, e não do candidato $g$.

$\varphi(n)$ informa quantas unidades existem módulo $n$ . Se existe uma raiz primitiva, o ciclo de potências de uma raiz primitiva tem comprimento $\varphi(n)$.

Ordem do candidato informa o comprimento do ciclo do candidato . Se a ordem for igual a $\varphi(n)$, o candidato é uma raiz primitiva . Se a ordem for menor, o candidato gera apenas parte do conjunto de unidades.

Não é uma unidade significa que o candidato não é coprimo do módulo. Nesse caso, o candidato não possui ordem multiplicativa no grupo de unidades e não pode ser uma raiz primitiva.

Raízes listadas: ignoradas significa que o módulo é maior que o limite de listagem selecionado. Isportanto não significa que as raízes primitivas não existam.

A sequência de potências começa com $k=0$, onde $g^0\equiv 1\pmod{n}$, e para no primeiro retorno a $1$. Quando o candidato é primitivo, ele visita cada unidade uma vez. Exibições com mais de 241 termos mostram apenas $k=0$ até $k=240$ e são explicitamente identificadas como truncadas.

Erros comuns e conceitos equivocados

Um erro comum é supor que todo módulo tem raízes primitivas. Muitos módulos, como $8$, $12$, $15$, e $16$, não têm.

Outro erro é testar um candidato que não é coprimo do módulo. Por exemplo, $g=6$ não pode ser uma raiz primitiva módulo $18$ porque $\gcd(6,18)=6$.

Alguns usuários confundem $n$ com $\varphi(n)$. O módulo controla os restos, mas $\varphi(n)$ controla a ordem máxima possível de uma unidade.

Também é fácil interpretar uma lista de raízes ignorada como um resultado negativo. Uma lista ignorada significa apenas que a calculadora não listou todas as raízes por causa do limite selecionado.

O arredondamento não faz parte da matemática aqui. Raízes primitivas, ordens, fatorações e resíduos são resultados inteiros exatos. Entradas decimais ou fracionárias não fazem parte deste cálculo.

Por fim, uma sequência de potências exibida pode não mostrar o ciclo completo. A ordem exata continua sendo informada, enquanto tabelas e gráficos longos param em $k=240$ e informam que o retorno em $k=\operatorname{ord}_n(g)$ não é exibido.

Quando usar raízes primitivas

Use raízes primitivas quando você quiser:

Verificar se um módulo tem um gerador para seus resíduos que são unidades.
Testar se um candidato específico $g$ gera todas as unidades módulo $n$.
Estudar a ordem multiplicativa e o comportamento cíclico na aritmética modular.
Comparar módulos primos, potências de primos e módulos compostos.
Desenvolver intuição sobre exemplos de logaritmos discretos e exponenciação modular.
Examinar sistemas reduzidos de resíduos por meio de uma sequência de potências.

As raízes primitivas são especialmente úteis para entender por que a multiplicação módulo $n$ pode se comportar de maneiras muito diferentes dependendo da fatoração de $n$.

Limitações e pontos importantes

Este cálculo usa aritmética modular com inteiros exatos. O módulo deve ser um inteiro de $2$ a $1,000,000,000$. Um candidato pode ser qualquer inteiro de $-1,000,000,000$ a $1,000,000,000$; ele é normalizado para seu resíduo canônico de $0$ até $n-1$.

O limite de listagem selecionado, de $20$ a $500$ controla apenas se todas as raízes primitivas serão enumeradas . Se $n$ for maior que esse limite, a calculadora ainda determina a existência, constrói uma raiz quando possível, calcula a ordem exata e informa a quantidade teórica de raízes $\varphi(\varphi(n))$.

Quando nenhum candidato é informado e existem raízes primitivas, a calculadora constrói e verifica uma raiz a partir da estrutura de potências de primos do módulo. Esta não é uma busca limitada por tentativas.

Ciclos completos de ordem no máximo $36$ usam um diagrama circular. Ciclos mais longos usam um gráfico de expoente versus resíduo. Tanto o gráfico quanto a tabela são limitados a $k=240$, e o expoente de retorno omitido é informado ao lado do resultado.

O método depende da fatoração de $n$ e $\varphi(n)$. A fatoração por divisão por tentativa é simples e confiável para valores moderados, mas pode ser mais lenta para entradas grandes permitidas do que métodos de fatoração mais avançados.

Multiplicações modulares grandes podem exigir suporte a aritmética exata de inteiros grandes no ambiente de cálculo . Se esse suporte não estiver disponível, produtos exatos muito grandes podem não ser processados.

Para criptografia, use isto apenas como ferramenta de aprendizado. A escolha de parâmetros criptográficos reais envolve requisitos de segurança adicionais, além de simplesmente encontrar uma raiz primitiva ou um gerador.

Como usar esta calculadora

Informe o módulo $n$ como um inteiro de $2$ a $1,000,000,000$.
Opcionalmente, informe um candidato inteiro $g$. Deixe-o em branco para construir e verificar automaticamente uma raiz primitiva quando existir.
Defina o limite de listagem de $20$ a $500$ . As raízes primitivas só são listadas quando $n$ não é maior que esse limite.
Use a opção show-powers para mostrar ou ocultar a sequência de potências do candidato.
Verifique se existem raízes primitivas para o módulo.
Verifique a ordem do candidato . Se ela for igual a $\varphi(n)$, o candidato é primitivo.
Examine $\varphi(n)$, a fatoração de $\varphi(n)$, as raízes listadas e as linhas da sequência de potências, quando disponíveis.
Experimente as predefinições de exemplo para comparar um caportanto primo, um caportanto sem raízes e um caportanto composto.
Se um gráfico for exibido e o download estiver disponível, use a opção PNG para salvar a visualização.

Perguntas frequentes

Todo módulo pode ter uma raiz primitiva?

Não. Para $n\ge 2$, as raízes primitivas existem apenas para $n=2$, $n=4$, potências de primos ímpares $p^k$, e potências de primos ímpares multiplicadas por dois $2p^k$. Um módulo como $8$ ou $12$ tem unidades, mas nenhuma unidade sozinha gera todas elas.

Por que o candidato deve ser coprimo do módulo?

As raízes primitivas pertencem ao grupo multiplicativo das unidades módulo $n$. Um número só é uma unidade quando é coprimo de $n$ . Se $\gcd(g,n)>1$, as potências de $g$ não conseguem gerar o sistema reduzido de resíduos.

Qual é a diferença entre ordem e raiz primitiva?

A ordem de $g$ módulo $n$ é o comprimento do ciclo antes de $g^d\equiv 1\pmod{n}$. Uma raiz primitiva é uma unidade cuja ordem é a maior possível, ou seja, $\varphi(n)$. Toda raiz primitiva tem uma ordem, mas nem toda unidade com uma ordem é primitiva.

Por que a sequência de potências começa em $k=0$?

A sequência começa em $g^0$, e $g^0\equiv 1\pmod{n}$ para qualquer unidade $g$ . Começar em $k=0$ deixa claro quando o ciclo começa e quando retorna a $1$.

Uma lista de raízes ignorada significa que não existem raízes primitivas?

Não. Uma lista ignorada significa que $n$ é maior que o limite de listagem selecionado, então a calculadora não enumerou todas as raízes. Use o resultado de existência e o resultado da ordem do candidato para entender o módulo e o candidato.

Uma raiz primitiva é o mesmo que um inverportanto modular?

Não. Um inverportanto modular de $g$ é um número que, multiplicado por $g$ dá $1$ módulo $n$. Uma raiz primitiva é uma unidade cujas potências geram todas as unidades módulo $n$.

Fontes e referências

Livros

William Stein. Elementary Number Theory: Primes, Congruences, and Secrets. Edição hospedada pelo autor, 23 de janeiro de 2017. Seções 2.1 e 2.5 sobre congruências, teorema de Euler, raízes primitivas e a estrutura de $({\mathbb Z}/p{\mathbb Z})^*$. https://wstein.org/ent/ent.pdf
Victor Shoup. A Computational Introduction to Number Theory and Algebra. Versão 2.5, Cambridge University Press / versão eletrônica hospedada pelo autor, 16 de maio de 2008. Seções 2.6, 2.7, 7.5 e 11.1–11.3 sobre a função phi de Euler, ordem multiplicativa, raízes primitivas, geradores, logaritmos discretos e fundamentos de Diffie-Hellman. https://www.shoup.net/ntb/ntb-v2_5.pdf

Fontes on-line e oficiais

National Institute of Standards and Technology. “§27.2 Functions.” NIST Digital Library of Mathematical Functions, Versão 1.2.7. Acesportanto em 4 de julho de 2026. https://dlmf.nist.gov/27.2
National Institute of Standards and Technology. “§27.16 Cryptography.” NIST Digital Library of Mathematical Functions, Versão 1.2.7. Acesportanto em 4 de julho de 2026. https://dlmf.nist.gov/27.16