El entero positivo k más pequeño tal que a^k ≡ 1 (mód n).
Toma un entero positivo $n$ y un entero $a$ tal que $\gcd(a, n) = 1$. El orden multiplicativo de $a$ módulo $n$, que escribimos como $\text{ord}_n(a)$, es el entero positivo más pequeño $k$ tal que $a^k \equiv 1 \pmod{n}$. Como $\gcd(a, n) = 1$, el Teorema de Euler garantiza que $a^{\phi(n)} \equiv 1 \pmod{n}$, lo que asegura que ese $k$ siempre existe y que $k \le \phi(n)$. Si $\gcd(a, n) \neq 1$, ninguna potencia de $a$ puede ser congruente a $1$ módulo $n$, y el orden no está definido.
Este concepto es fundamental para entender la estructura cíclica de las potencias en aritmética modular. La sucesión de potencias $a, a^2, a^3, \dots \pmod{n}$ es periódica con periodo $k = \text{ord}_n(a)$. Esta periodicidad te permite reducir exponentes grandes módulo $k$. Por ejemplo, para calcular $a^x \pmod{n}$, solo necesitas calcular $a^{x \pmod k} \pmod{n}$. Esta es una herramienta muy potente para resolver problemas con congruencias exponenciales y para encontrar las últimas cifras de números muy grandes.
Un punto clave es que, aunque el Teorema de Euler te dice que $a^{\phi(n)} \equiv 1 \pmod{n}$, $\phi(n)$ no es necesariamente el exponente más pequeño. El orden real $\text{ord}_n(a)$ tiene que ser un divisor de $\phi(n)$. Cuando $\text{ord}_n(a) = \phi(n)$, a $a$ se le llama raíz primitiva módulo $n$, lo que significa que las potencias de $a$ generan todos los residuos coprimos módulo $n$.
Definición: $$k = \text{ord}_n(a) \iff (a^k \equiv 1 \pmod n \text{ y } a^m \not\equiv 1 \pmod n \text{ para todo } 1 \le m < k)$$
Propiedad Fundamental de Divisibilidad: Para cualquier entero $x > 0$, $$a^x \equiv 1 \pmod n \iff \text{ord}_n(a) \mid x$$
Corolario (Teorema de Euler): Como $a^{\phi(n)} \equiv 1 \pmod n$, se sigue que: $$\text{ord}_n(a) \mid \phi(n)$$
Orden de una Potencia: Si $\text{ord}_n(a) = k$, entonces el orden de $a^h$ módulo $n$ es: $$\text{ord}_n(a^h) = \frac{k}{\gcd(h, k)}$$
Congruencia de Potencias: $$a^x \equiv a^y \pmod n \iff x \equiv y \pmod{\text{ord}_n(a)}$$
Teorema: Sea $k = \text{ord}_n(a)$. Entonces $a^x \equiv 1 \pmod n$ si y solo si $k \mid x$.
Demostración:
$(\Longleftarrow)$ Supón que $k \mid x$. Entonces existe un entero $m$ tal que $x = mk$. Puedes escribir: $$a^x = a^{mk} = (a^k)^m$$ Por la definición de orden, $a^k \equiv 1 \pmod n$. Al sustituir esto en la ecuación: $$(a^k)^m \equiv 1^m \equiv 1 \pmod n$$ Así que $a^x \equiv 1 \pmod n$.
$(\Longrightarrow)$ Supón que $a^x \equiv 1 \pmod n$. Por el Algoritmo de la División, puedes dividir $x$ entre $k$ para obtener un cociente $q$ y un residuo $r$: $$x = qk + r, \quad \text{donde } 0 \le r < k$$ Ahora, considera la potencia $a^x$: $$a^x = a^{qk + r} = (a^k)^q \cdot a^r$$ Como $a^x \equiv 1 \pmod n$ (por suposición) y $a^k \equiv 1 \pmod n$ (por definición de orden), tienes que: $$1 \equiv (1)^q \cdot a^r \pmod n$$ $$1 \equiv a^r \pmod n$$ Aquí has llegado a que $a^r \equiv 1 \pmod n$ con $0 \le r < k$. Sin embargo, $k$ está definido como el entero positivo más pequeño tal que $a^k \equiv 1 \pmod n$. Si $r > 0$, entonces $r$ sería un entero positivo más chico que $k$ que cumple la congruencia, lo cual contradice que $k$ sea el mínimo. Por lo tanto, la única posibilidad es que $r = 0$. Como $r = 0$, tienes que $x = qk$, lo que implica que $k \mid x$.
$\square$