ord(aᵏ) = ord(a)/mcd(k,ord(a)).
El orden multiplicativo de un entero $a$ módulo $n$, que escribimos como $\text{ord}_n(a)$, es el entero positivo más pequeño $d$ tal que $a^d \equiv 1 \pmod{n}$. Una pregunta fundamental en teoría de números tiene que ver con cómo cambia este orden cuando elevas la base $a$ a una potencia $k$. Específicamente, si conoces el orden de $a$, ¿puedes determinar el orden de $a^k$? La propiedad $\text{ord}_n(a^k) = \frac{\text{ord}_n(a)}{\gcd(k, \text{ord}_n(a))}$ te da una fórmula directa para este cálculo.
Este concepto es parecido a "acelerar" el movimiento alrededor de un ciclo. Si las potencias de $a$ generan un ciclo de longitud $d$, entonces las potencias de $a^k$ representan dar pasos de tamaño $k$ dentro de ese ciclo. Si $k$ es primo relativo con $d$, la nueva secuencia visita cada elemento del ciclo original (solo que en un orden diferente), manteniendo la longitud del ciclo. Pero si $k$ comparte un factor común con $d$, los pasos se sincronizan con la longitud del ciclo más rápido, lo que resulta en un periodo más corto.
Esta propiedad aparece por todos lados en las matemáticas de olimpiada, sobre todo en problemas que involucran raíces primitivas y congruencias exponenciales. Te permite calcular el orden de