Calculadora de orden multiplicativo módulo n

Introduzca una base entera a y un módulo n; el resultado incluye la base reducida, el indicador de Euler, el orden y una comprobación modular directa. El cálculo solo está definido cuando a y n son coprimos, por lo que los pares no válidos generan un error claro en lugar de un número engañoso. Resulta útil en ejercicios de aritmética modular, análisis de subgrupos cíclicos, patrones periódicos y teoría elemental de números.

Qué significa el orden multiplicativo

Para los enteros a y n, el orden multiplicativo de a módulo n es el menor entero positivo k tal que a^k deja resto 1 al dividirse entre n. La expresión «menor positivo» es esencial: otros exponentes posteriores también pueden producir 1, pero el orden señala el primer retorno a la identidad en la multiplicación modular. Por ejemplo, las potencias de 2 módulo 9 tienen residuos 2, 4, 8, 7, 5 y, finalmente, 1; por tanto, el orden es 6. Este concepto describe el tamaño del subgrupo cíclico generado por a dentro de las clases de residuos invertibles módulo n. La calculadora reduce a a su residuo no negativo estándar antes de operar, de modo que trata de forma coherente las bases negativas y las mayores que n. También devuelve un valor de comprobación calculado con el orden obtenido. Un resultado de 1 confirma la congruencia definitoria, mientras que el proceso de reducción garantiza que ningún divisor propio restante del exponente candidato pueda satisfacerla.

Por qué se exige que sean coprimos

El orden multiplicativo módulo n solo existe cuando gcd(a, n) es 1. No se trata de una simple convención de entrada. Un elemento debe tener inverso multiplicativo módulo n para que sus potencias pertenezcan al grupo finito de unidades y puedan regresar a 1. Si a y n comparten un factor, toda potencia positiva de a conserva un obstáculo de divisibilidad compatible y no puede ser congruente con 1 módulo n. La calculadora comprueba esta condición de inmediato e indica el máximo común divisor real cuando no se cumple. Además, el módulo debe ser al menos 2, pues el problema habitual del orden se plantea en un sistema de residuos no trivial. La base puede ser cero, negativa o positiva dentro del límite publicado, aunque cero no es válido para ningún módulo permitido porque nunca es coprimo con n. Al preparar la entrada, utilice enteros exactos, no decimales ni aproximaciones científicas. Así se conserva la aritmética discreta de la que dependen el máximo común divisor, la factorización y las potencias modulares.

Cómo se obtiene el exponente mínimo

La calculadora no prueba todos los exponentes de manera sucesiva. Primero factoriza n lo necesario para calcular el indicador de Euler phi(n). El teorema de Euler garantiza que a elevado a phi(n) es congruente con 1 siempre que gcd(a, n) sea 1, por lo que el orden buscado debe dividir a phi(n). Después, el algoritmo factoriza phi(n) y comprueba repetidamente si dividir el candidato actual por uno de sus factores primos sigue dando una potencia modular igual a 1. Cuando ocurre, el candidato menor sustituye al anterior. Cuando ya no se puede retirar ningún factor primo, el candidato restante es el orden multiplicativo. La exponenciación modular emplea cuadrados sucesivos y mantiene los valores intermedios reducidos módulo n; toda la aritmética entera es exacta. Este método es mucho más rápido que recorrer cada exponente positivo, sobre todo si el orden es grande. Las entradas están limitadas a un billón para que la división de prueba tenga un techo determinista claro, adecuado tanto para la herramienta del navegador como para llamadas API automatizadas.