El orden de $a$ módulo $p^k$: fórmulas exactas

La pregunta precisa

Conocemos el orden de $a$ módulo $p$. ¿Cómo se relaciona con el orden módulo $p^2$, $p^3$, y en general $p^k$?

La respuesta no es obvia: el orden módulo $p^2$ puede ser igual al orden módulo $p$, o puede ser $p$ veces más grande. Y la "decisión" de cuál ocurre está codificada en la valuación $v_p(a^{\text{ord}_p(a)} - 1)$.

Este bloque desarrolla la fórmula general. Es una de las herramientas más potentes para problemas IMO de nivel 6 de Teoría de Números.

La fórmula central

Sea $p$ primo impar, $a$ un entero con $\gcd(a, p) = 1$. Sea $d = \text{ord}_p(a)$ y $e = v_p(a^d - 1) \ge 1$ (notar que $e \ge 1$ porque $p \mid a^d - 1$ por definición del orden módulo $p$).

Entonces para todo $k \ge 1$:

En palabras: el orden módulo $p^k$ es igual al orden módulo $p$ multiplicado por $p^{\max(0, k-e)}$. Cuando $k \le e$, el orden no crece al subir de $p$ a $p^k$. Cuando $k > e$, el orden crece por un factor de $p$ con cada potencia adicional de $p$.

Demostración de la fórmula

Necesitamos encontrar el mínimo $n$ tal que $p^k \mid a^n - 1$.

Paso 1. Escribimos $n = d \cdot q + r$ con $0 \le r < d$. Entonces $a^n = (a^d)^q \cdot a^r$. Como $p \mid a^d - 1$, si $r \ne 0$ entonces $p \nmid a^r - 1$ (pues $d$ es el orden mínimo módulo $p$ y $r < d$). Si $p \mid a^n - 1$ y $p \nmid a^r - 1$, entonces $p \nmid (a^d)^q \cdot a^r - 1$... Más directamente: $a^n \equiv 1 \pmod{p}$ implica $p \mid a^n - 1$ implica $d \mid n$ (por definición de orden). Así $n = d \cdot m$ para algún entero positivo $m$.

Paso 2. Ahora necesitamos el mínimo $m$ tal que $p^k \mid a^{dm} - 1 = (a^d)^m - 1$. Llamemos $b = a^d$. Entonces $b \equiv 1 \pmod{p}$ y $v_p(b - 1) = e$. Aplicamos LTE a $b^m - 1^m$: como $p \mid b - 1$ y $p \nmid b$, $p \nmid 1$, obtenemos $v_p(b^m - 1) = v_p(b - 1) + v_p(m) = e + v_p(m)$.

Paso 3. La condición $p^k \mid b^m - 1$ equivale a $e + v_p(m) \ge k$, es decir, $v_p(m) \ge k - e$. El mínimo $m$ con esta propiedad es $m = p^{\max(0, k-e)}$.

Conclusión. El mínimo $n$ es $d \cdot p^{\max(0, k-e)}$, que es $\text{ord}_{p^k}(a)$. $\square$

Los dos casos: $e = 1$ versus $e \ge 2$

El valor de $e = v_p(a^d - 1)$ determina completamente el comportamiento del orden al elevar la potencia.

**Caso genérico $e = 1$.** Este es el caso más frecuente. Para $k \ge 2$: $\text{ord}_{p^k}(a) = d \cdot p^{k-1}$. El orden crece exactamente por un factor de $p$ con cada nivel. En particular, si $a$ es raíz primitiva módulo $p$ (es decir, $d = p-1$), entonces con $e = 1$ es raíz primitiva módulo $p^k$ para todo $k$, con orden $p^{k-1}(p-1)$.

**Caso especial $e \ge 2$.** Si $v_p(a^d - 1) = e \ge 2$, entonces para $k \le e$ el orden módulo $p^k$ es el mismo $d$ que módulo $p$. El orden no crece hasta que $k$ supera $e$. Estos elementos se llaman a veces "Wieferich-like" para el primo $p$ y base $a$: su comportamiento es anómalo.

**La rareza de $e \ge 2$.** Heurísticamente, para $a$ fijo y $p$ primo aleatorio, la condición $p^2 \mid a^{p-1} - 1$ (cuando $d = p-1$) ocurre con probabilidad $\approx 1/p$, muy rara. Los únicos $p$ conocidos con $2^{p-1} \equiv 1 \pmod{p^2}$ son $p = 1093$ y $p = 3511$ (primos de Wieferich).

Ejemplo: orden de 2 módulo $3^k$

Calculemos $\text{ord}_{3^k}(2)$ para todo $k \ge 1$.

Primero, $\text{ord}_3(2) = 2$ (pues $2^2 = 4 \equiv 1 \pmod{3}$ y $2^1 = 2 \not\equiv 1$). Así $d = 2$.

Ahora $a^d - 1 = 2^2 - 1 = 3$, entonces $e = v_3(3) = 1$.

Por la fórmula: $\text{ord}_{3^k}(2) = 2 \cdot 3^{\max(0, k-1)} = 2 \cdot 3^{k-1}$ para $k \ge 1$.

Verificación: $\text{ord}_3(2) = 2$ ✓. $\text{ord}_9(2) = 6$: efectivamente, $2^6 = 64 = 63 + 1 = 7 \cdot 9 + 1 \equiv 1 \pmod{9}$ ✓, y $2^3 = 8 \equiv -1 \not\equiv 1 \pmod{9}$ ✓. $\text{ord}_{27}(2) = 18$: $2^{18} = 2^{10} \cdot 2^8 = 1024 \cdot 256 = 262144 = 9709 \cdot 27 + 1$ ✓.

Este cálculo aparece directamente en problemas como "hallar todos los $n$ con $3^k \mid 2^n - 1$": la respuesta es exactamente los múltiplos de $\text{ord}_{3^k}(2) = 2 \cdot 3^{k-1}$.

La fórmula para $p = 2$

Para el primo $p = 2$ la situación es más delicada por la no ciclicidad de $(\mathbb{Z}/2^k\mathbb{Z})^*$ para $k \ge 3$.

Para $a$ impar y $k \ge 3$: si $a \equiv 1 \pmod{4}$ (es decir, $v_2(a-1) \ge 2$), entonces $\text{ord}_{2^k}(a) = 2^{k - v_2(a-1)}$ (cuando $v_2(a-1) \le k$).

Si $a \equiv 3 \pmod{4}$ (es decir, $a \equiv -1 \pmod{4}$), entonces $\text{ord}_{2^k}(a) = 2$ para $k = 2$ y $\text{ord}_{2^k}(a^2)$ sigue la fórmula del caso anterior para $k \ge 3$.

Estas fórmulas son menos elegantes que el caso impar, pero su derivación sigue el mismo principio: LTE + inducción en $k$. En la lección de problemas (4.4) veremos ejemplos concretos con $p = 2$.