Propiedad de que ord(a) | φ(n).
La idea de que el orden multiplicativo divide a la función totiente de Euler es un resultado fundamental en la teoría de números elemental, y sirve como un refinamiento del Teorema de Euler. Para un entero $n > 1$ y un entero $a$ coprimo con $n$, el orden multiplicativo de $a$ módulo $n$, que escribimos como $\text{ord}_n(a)$, lo definimos como el entero positivo más pequeño $k$ tal que $a^k \equiv 1 \pmod{n}$. Aunque el Teorema de Euler garantiza que $a^{\phi(n)} \equiv 1 \pmod{n}$, no asegura que $\phi(n)$ sea el exponente más pequeño. Este tema establece que el orden real tiene que ser un divisor de $\phi(n)$.
Esta propiedad es clave para resolver congruencias exponenciales de grado alto y te sirve para determinar la existencia de raíces primitivas. En las olimpiadas de matemáticas, la vas a usar mucho para reducir el espacio de búsqueda del orden de un elemento. En lugar de revisar cada entero, solo tienes que checar los divisores de $\phi(n)$. Además, este concepto te da la condición necesaria para saber si un número $a$ es una raíz primitiva módulo $n$; $a$ es una raíz primitiva si y solo si $\text{ord}_n(a) = \phi(n)$.
Desde una perspectiva algebraica, este resultado es un caso específico del Teorema de