Todas as raízes primitivas módulo 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. 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

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 resposta informa n, o totiente de Euler phi, a quantidade de raízes primitivas e o array primitive_roots em ordem numérica. 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. 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. Informe n como inteiro ou cadeia decimal simples. Solicitações bem-sucedidas custam US$ 0,002; entradas incompatíveis ou malformadas são identificadas claramente.