Existencia de raíces primitivas módulo $p^k$

Recapitulación: qué sabemos de $p$ y hacia dónde vamos

En el Nivel 2 demostramos que para todo primo $p$ existe una raíz primitiva módulo $p$: un entero $g$ con $\text{ord}_p(g) = p-1$. Esto equivale a decir que el grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^*$ es cíclico de orden $p-1$.

La pregunta natural —y la que separa el Nivel 2 del Nivel 3— es: ¿qué pasa con $(\mathbb{Z}/p^k\mathbb{Z})^*$ para $k \ge 2$? Este grupo tiene orden $\phi(p^k) = p^{k-1}(p-1)$. ¿También es cíclico? ¿Existe un $g$ con $\text{ord}_{p^k}(g) = p^{k-1}(p-1)$?

La respuesta es sí para todo primo impar $p$ y todo $k \ge 1$. La demostración tiene dos pasos: primero levantamos de $p$ a $p^2$, luego de $p^{k-1}$ a $p^k$ por inducción. Ambos pasos usan el mismo mecanismo —una versión del LTE que ya conocemos bien— pero aplicado de manera estructural.

Paso 1: de una raíz primitiva mod $p$ a una mod $p^2$

Sea $g$ una raíz primitiva módulo $p$, es decir, $\text{ord}_p(g) = p-1$. Queremos encontrar una raíz primitiva módulo $p^2$.

Afirmación: $g$ mismo, o bien $g + p$, es una raíz primitiva módulo $p^2$.

Sea $d = \text{ord}_{p^2}(g)$. Como $g^d \equiv 1 \pmod{p^2}$ implica $g^d \equiv 1 \pmod{p}$, tenemos que $d$ es divisible por $\text{ord}_p(g) = p-1$. Por otro lado, $d \mid \phi(p^2) = p(p-1)$. Entonces $d \in \{p-1, p(p-1)\}$.

Si $d = p(p-1)$, ya terminamos: $g$ es raíz primitiva módulo $p^2$. Si $d = p-1$, entonces $g^{p-1} \equiv 1 \pmod{p^2}$. En este caso, consideramos $g' = g + p$. Calculamos $g'^{p-1}$ módulo $p^2$ usando el binomio: $g'^{p-1} = (g+p)^{p-1} = g^{p-1} + (p-1)g^{p-2} \cdot p + O(p^2) \equiv 1 + (p-1)p g^{p-2} \pmod{p^2}$.

El término $(p-1)p g^{p-2} \equiv -p g^{p-2} \pmod{p^2}$. Como $p \nmid g$, tenemos $p \nmid g^{p-2}$, así que $g'^{p-1} \equiv 1 - p g^{p-2} \not\equiv 1 \pmod{p^2}$. Esto implica que $\text{ord}_{p^2}(g') \ne p-1$, luego $\text{ord}_{p^2}(g') = p(p-1) = \phi(p^2)$. Así $g'$ es raíz primitiva módulo $p^2$.

Paso 2: de $p^{k-1}$ a $p^k$ por inducción

Supongamos que $g$ es raíz primitiva módulo $p^{k-1}$, es decir, $\text{ord}_{p^{k-1}}(g) = p^{k-2}(p-1)$. Queremos probar que $g$ (o una modificación suya) es raíz primitiva módulo $p^k$.

Sea $d = \text{ord}_{p^k}(g)$. El mismo argumento de antes da $d \mid \phi(p^k) = p^{k-1}(p-1)$ y $(p-1) \mid d$. Además, de $g^d \equiv 1 \pmod{p^k}$ se deduce $g^d \equiv 1 \pmod{p^{k-1}}$, así $p^{k-2}(p-1) \mid d$. Combinando, $d \in \{p^{k-2}(p-1), p^{k-1}(p-1)\}$.

El resultado clave es que si $g$ es una raíz primitiva de $p$ con $g^{p-1} \not\equiv 1 \pmod{p^2}$ (lo cual garantizamos en el Paso 1 eligiendo $g$ o $g+p$), entonces $g$ es raíz primitiva módulo $p^k$ para todo $k \ge 1$.

La demostración usa LTE: como $g^{p-1} = 1 + mp$ con $p \nmid m$ (condición del Paso 1), para calcular $\text{ord}_{p^k}(g)$ necesitamos el mínimo $n$ con $g^n \equiv 1 \pmod{p^k}$. Esto equivale a $p^k \mid g^n - 1$. Por LTE aplicado a $g^{p-1} = (1+mp)^{p^{k-2}}$ —ver el siguiente bloque—, se obtiene que $v_p(g^{p^{k-2}(p-1)} - 1) = k-1 < k$, así $p^k \nmid g^{p^{k-2}(p-1)} - 1$, y por tanto $\text{ord}_{p^k}(g) \nmid p^{k-2}(p-1)$. Concluimos $\text{ord}_{p^k}(g) = p^{k-1}(p-1)$.

El argumento LTE que cierra la inducción

El ingrediente técnico es calcular $v_p(g^{p^{j}(p-1)} - 1)$ para $j = 0, 1, \ldots, k-1$.

Escribamos $h = g^{p-1}$. La hipótesis del Paso 1 garantiza $h = 1 + mp$ con $p \nmid m$, es decir, $v_p(h - 1) = 1$.

Ahora $g^{p^j(p-1)} = h^{p^j}$. Aplicamos LTE a $h^{p^j} - 1^{p^j}$ con $a = h$, $b = 1$, primo $p$: verificamos $p \mid h - 1 = mp$ (sí), $p \nmid h$ (sí, pues $h \equiv 1 \pmod{p}$ y $p \nmid 1 = b$). Entonces:

$v_p(h^{p^j} - 1) = v_p(h - 1) + v_p(p^j) = 1 + j$.

En particular, $v_p(g^{p^j(p-1)} - 1) = 1 + j$. Para $j = k-2$: $v_p(g^{p^{k-2}(p-1)} - 1) = k-1 < k$, así $p^k \nmid g^{p^{k-2}(p-1)} - 1$, confirmando que $\text{ord}_{p^k}(g) \nmid p^{k-2}(p-1)$. Para $j = k-1$: $v_p(g^{p^{k-1}(p-1)} - 1) = k$, así $p^k \mid g^{\phi(p^k)} - 1$, confirmando que $g^{\phi(p^k)} \equiv 1 \pmod{p^k}$. Todo cuadra.

Consecuencias estructurales para olimpiadas

El teorema que acabamos de demostrar tiene consecuencias directas en problemas IMO de nivel 6:

1. Representación de residuos. Todo entero $a$ con $\gcd(a, p) = 1$ se escribe como $a \equiv g^j \pmod{p^k}$ para un único $j \in \{0, 1, \ldots, p^{k-1}(p-1)-1\}$. Esto es el índice o logaritmo discreto módulo $p^k$.

**2. Solubilidad de $x^n \equiv a \pmod{p^k}$.** Usando la raíz primitiva, $a = g^s$ y $x = g^t$, la ecuación se convierte en $nt \equiv s \pmod{p^{k-1}(p-1)}$. Es soluble si y solo si $\gcd(n, p^{k-1}(p-1)) \mid s$.

**3. Orden exacto módulo $p^k$.** Si $\text{ord}_p(a) = d$ y $v_p(a^d - 1) = e$ (con $e \ge 1$ asegurado por el LTE), entonces $\text{ord}_{p^k}(a) = d \cdot p^{\max(0, k-e)}$. Esta fórmula es la herramienta central de la Lección 4.3.

En la siguiente lección construimos sobre esta base la teoría de índices y logaritmos discretos, la cual transforma ecuaciones modulares complicadas en congruencias lineales.

Nota sobre $p = 2$: el caso excepcional

Para el primo $p = 2$, el grupo $(\mathbb{Z}/2^k\mathbb{Z})^*$ no es cíclico para $k \ge 3$. En lugar de ser cíclico de orden $2^{k-1}$, es isomorfo a $\mathbb{Z}/2 \times \mathbb{Z}/2^{k-2}$.

El generador de la parte cíclica principal es $g = 3$: se puede verificar que $3^{2^{k-2}} \equiv 1 \pmod{2^k}$ y $3^{2^{k-3}} \not\equiv 1 \pmod{2^k}$ para $k \ge 3$, así $\text{ord}_{2^k}(3) = 2^{k-2}$. El factor $\mathbb{Z}/2$ adicional está generado por $-1 \equiv 2^k - 1$.

Esta diferencia estructural explica por qué muchos argumentos de raíces primitivas mod $p^k$ requieren separar los casos $p$ impar y $p = 2$. En los problemas de olimpiadas, si el enunciado dice "sea $p$ un primo" sin restricción, hay que verificar el caso $p = 2$ por separado.