Probando con los divisores de φ(n).
El orden multiplicativo de un entero $a$ módulo $n$, que escribes como $\text{ord}_n(a)$, es el entero positivo más pequeño $k$ tal que $a^k \equiv 1 \pmod n$. Este concepto solo está definido cuando $\gcd(a, n) = 1$. Aunque la definición sugiere que podrías simplemente calcular $a^1, a^2, a^3, \dots$ hasta que el resultado sea $1$, este enfoque de fuerza bruta es muy ineficiente si $n$ es grande. El método eficiente para calcular el orden usa el Teorema de Lagrange y el Teorema de Euler, que restringen los posibles valores del orden.
Específicamente, el Teorema de Euler dice que $a^{\phi(n)} \equiv 1 \pmod n$. Una propiedad fundamental del orden es que si $a^m \equiv 1 \pmod n$, entonces $\text{ord}_n(a)$ tiene que dividir a $m$. Por lo tanto, $\text{ord}_n(a)$ tiene que ser un divisor de $\phi(n)$. Para calcular el orden de forma eficiente, primero calcula $\phi(n)$ y encuentra sus divisores. Luego, prueba estos divisores $d$ (normalmente de menor a mayor) para encontrar el más pequeño que cumpla $a^d \equiv 1 \pmod n$.
Esta técnica aparece muchísimo en las matemáticas de competencia, sobre todo en problemas