Calculadora de ordem multiplicativa módulo n

Informe uma base inteira a e um módulo n; o resultado inclui a base reduzida, a função totiente de Euler, a ordem e uma verificação modular direta. O cálculo só é definido quando a e n são coprimos, portanto pares inválidos geram um erro claro, e não um número enganoso. A ferramenta é útil em exercícios de aritmética modular, análise de subgrupos cíclicos, padrões periódicos e teoria elementar dos números.

O significado da ordem multiplicativa

Para os inteiros a e n, a ordem multiplicativa de a módulo n é o menor inteiro positivo k tal que a^k deixa resto 1 na divisão por n. A expressão “menor positivo” é importante: expoentes posteriores também podem produzir 1, mas a ordem marca o primeiro retorno à identidade na multiplicação modular. Por exemplo, as potências de 2 módulo 9 apresentam os resíduos 2, 4, 8, 7, 5 e, depois, 1; logo, a ordem é 6. O conceito descreve o tamanho do subgrupo cíclico gerado por a entre as classes de resíduos invertíveis módulo n. Antes de calcular, a ferramenta reduz a ao seu resíduo não negativo padrão, tratando de maneira consistente bases negativas e bases maiores que n. Ela também retorna um valor de conferência calculado com a ordem informada. O valor 1 confirma a congruência que define a ordem, enquanto o processo de redução garante que nenhum divisor próprio ainda presente no expoente candidato possa satisfazê-la.

Por que a coprimalidade é necessária

A ordem multiplicativa módulo n só existe quando gcd(a, n) é 1. Isso não é apenas uma convenção de entrada. Um elemento precisa ter inverso multiplicativo módulo n para que suas potências pertençam ao grupo finito das unidades e possam voltar a 1. Se a e n compartilham um fator, toda potência positiva de a mantém um obstáculo de divisibilidade compatível e não pode ser congruente a 1 módulo n. A calculadora testa essa condição imediatamente e informa o máximo divisor comum efetivo quando ela não é atendida. O módulo também deve ser pelo menos 2, pois o problema usual da ordem é formulado em um sistema de resíduos não trivial. A base pode ser zero, negativa ou positiva dentro do limite publicado, porém zero não funciona com nenhum módulo permitido porque nunca é coprimo com n. Ao preparar a entrada, use inteiros exatos, em vez de decimais ou aproximações científicas. Isso preserva a aritmética discreta da qual dependem o máximo divisor comum, a fatoração e as potências modulares.

Como a calculadora encontra o menor expoente

A calculadora não testa todos os expoentes em sequência. Primeiro, ela fatora n o suficiente para calcular a função totiente de Euler phi(n). O teorema de Euler garante que a elevado a phi(n) é congruente a 1 quando gcd(a, n) é 1; portanto, a ordem procurada deve dividir phi(n). Em seguida, o algoritmo fatora phi(n) e verifica repetidamente se a divisão do candidato atual por um de seus fatores primos ainda produz uma potência modular igual a 1. Sempre que isso acontece, o candidato menor substitui o anterior. Quando nenhum fator primo pode mais ser removido, o candidato restante é a ordem multiplicativa. A exponenciação modular usa quadrados sucessivos, mantendo os valores intermediários reduzidos módulo n, e toda a aritmética inteira permanece exata. Essa abordagem é muito mais rápida do que percorrer cada expoente positivo, especialmente quando a ordem é grande. As entradas são limitadas a um trilhão, garantindo que a fatoração por tentativa tenha um teto determinístico claro, apropriado tanto para a ferramenta no navegador quanto para chamadas automatizadas à API.