Orden de un elemento módulo n

El Teorema de Euler ya no es suficiente

En el Capítulo 2 aprendimos que $a^{\varphi(n)} \equiv 1 \pmod{n}$ cuando $\gcd(a,n)=1$. Esto permite reducir exponentes: $a^k \equiv a^{k \bmod \varphi(n)} \pmod{n}$. Sin embargo, $\varphi(n)$ no es siempre el exponente mínimo. Para $a=1$ y cualquier $n$, tenemos $1^1 \equiv 1 \pmod{n}$, pero $\varphi(n)$ puede ser tan grande como $n-1$.

La pregunta más precisa es: ¿cuál es el menor exponente positivo $k$ tal que $a^k \equiv 1 \pmod{n}$? Esta cantidad captura la verdadera periodicidad de las potencias de $a$, y tiene propiedades algebraicas mucho más ricas que $\varphi(n)$.

Conocer el orden exacto de un elemento es la diferencia entre una solución elegante y un cálculo interminable. En problemas olímpicos, el orden multiplicativo aparece cada vez que la pregunta involucra periodicidad de potencias, divisibilidad de exponentes, o existencia de soluciones de ecuaciones modulares.

Definición y ejemplos

Sea $n \ge 2$ un entero y $a$ un entero con $\gcd(a,n)=1$. El **orden multiplicativo de $a$ módulo $n$**, denotado $\text{ord}_n(a)$, es el menor entero positivo $d$ tal que $a^d \equiv 1 \pmod{n}$.

La existencia de $d$ está garantizada: por el Teorema de Euler, $a^{\varphi(n)} \equiv 1 \pmod{n}$, así que el conjunto $\{k \ge 1 : a^k \equiv 1 \pmod{n}\}$ es no vacío y tiene un mínimo.

Ejemplo 1: $a = 2$, $n = 7$. Calculamos $2^1=2$, $2^2=4$, $2^3=8\equiv 1 \pmod{7}$. Entonces $\text{ord}_7(2) = 3$. Nótese que $\varphi(7)=6=2\cdot 3$, así el orden es la mitad del exponente de Euler.

Ejemplo 2: $a = 3$, $n = 7$. Calculamos $3^1=3$, $3^2=9\equiv 2$, $3^3=6$, $3^4=18\equiv 4$, $3^5=12\equiv 5$, $3^6=15\equiv 1 \pmod{7}$. Entonces $\text{ord}_7(3) = 6 = \varphi(7)$. El 3 "usa" todo el espacio disponible.

Teorema fundamental: el orden divide a cualquier exponente que da 1

El resultado más importante sobre el orden es el siguiente: si $a^m \equiv 1 \pmod{n}$, entonces $\text{ord}_n(a) \mid m$. En particular, $\text{ord}_n(a) \mid \varphi(n)$.

Demostración. Sea $d = \text{ord}_n(a)$. Dividimos $m = qd + r$ con $0 \le r < d$. Entonces $a^m = (a^d)^q \cdot a^r \equiv 1^q \cdot a^r = a^r \pmod{n}$. Si $a^m \equiv 1$, obtenemos $a^r \equiv 1 \pmod{n}$. Pero $0 \le r < d$ y $d$ es el mínimo exponente positivo con $a^d \equiv 1$. La única posibilidad es $r = 0$, es decir $d \mid m$.

Como consecuencia, la sucesión $a^1, a^2, a^3, \ldots$ módulo $n$ es **periódica con período exacto $d$**. Las primeras $d$ potencias $a^1, a^2, \ldots, a^d = 1$ son todas distintas módulo $n$ (si $a^i \equiv a^j$ con $i < j \le d$, entonces $a^{j-i} \equiv 1$ con $0 < j-i < d$, contradiciendo la minimalidad de $d$).

Esta propiedad tiene una consecuencia sorprendente: $\text{ord}_n(a)$ siempre divide a $\varphi(n)$, lo que restringe fuertemente los posibles valores del orden. Para encontrar $\text{ord}_7(a)$, por ejemplo, solo necesitamos probar los divisores de $\varphi(7)=6$, que son $1, 2, 3, 6$.

El orden de las potencias

Una fórmula muy útil: $\text{ord}_n(a^k) = \dfrac{\text{ord}_n(a)}{\gcd(\text{ord}_n(a),\, k)}$.

Demostración. Sea $d = \text{ord}_n(a)$ y $e = \gcd(d, k)$. Calculamos el orden de $a^k$: queremos el menor $m > 0$ con $(a^k)^m \equiv 1 \pmod{n}$, es decir $a^{km} \equiv 1$, lo que por el teorema anterior equivale a $d \mid km$. Esto es $\frac{d}{e} \mid \frac{k}{e} \cdot m$. Como $\gcd(d/e, k/e) = 1$ (dividimos por el mcd), obtenemos $\frac{d}{e} \mid m$. El mínimo tal $m$ es $m = d/e$.

Corolario importante: $\text{ord}_n(a^k) = \text{ord}_n(a)$ si y solo si $\gcd(k, \text{ord}_n(a)) = 1$. Es decir, elevar $a$ a una potencia coprima con su orden no cambia el orden.

Aplicación: si $\text{ord}_7(3) = 6$ (como calculamos antes), entonces $\text{ord}_7(3^2) = 6/\gcd(6,2) = 6/2 = 3$ y $\text{ord}_7(3^3) = 6/\gcd(6,3) = 6/3 = 2$. Esto coincide con $3^3 = 27 \equiv 6 \equiv -1 \pmod{7}$, que tiene orden 2.

Orden y ecuaciones modulares

El orden también resuelve preguntas del tipo: ¿para cuáles $k$ se cumple $a^k \equiv a^j \pmod{n}$? La respuesta es: $a^k \equiv a^j \pmod{n}$ si y solo si $k \equiv j \pmod{\text{ord}_n(a)}$. Esto convierte muchas ecuaciones exponenciales en congruencias lineales.

Aplicación olímpica típica: ¿para cuáles $n$ se cumple $3^n \equiv 5 \pmod{7}$? Buscamos $n$ tal que $3^n \equiv 5 \pmod 7$. La sucesión de potencias de $3$ módulo $7$ es $3, 2, 6, 4, 5, 1, 3, 2, \ldots$ con período $6$. El valor $5$ aparece en la posición $5$ (es decir, $3^5 \equiv 5 \pmod 7$). Entonces las soluciones son exactamente $n \equiv 5 \pmod{6}$.

Nótese que este tipo de argumento es mucho más preciso que el Teorema de Euler: Euler nos diría que el período divide a $6$, pero solo calculando el orden exacto sabemos si es $1, 2, 3$ o $6$.