Raíces primitivas

Cuando el orden es máximo

Recordando los ejemplos de la lección anterior: $\text{ord}_7(2) = 3$ mientras que $\text{ord}_7(3) = 6 = \varphi(7)$. El elemento $3$ tiene el orden más grande posible —su período es exactamente $\varphi(7)$— y al calcular sus potencias recorremos todos los enteros de $1$ a $6$ módulo $7$.

Este comportamiento tiene un nombre y un poder especial. Un entero $g$ con $\gcd(g,n)=1$ es una **raíz primitiva módulo $n$** si $\text{ord}_n(g) = \varphi(n)$. Equivalentemente, $g$ es raíz primitiva si las potencias $g^1, g^2, \ldots, g^{\varphi(n)}$ recorren todas las clases de residuos coprimas con $n$.

Cuando $n = p$ es primo, $\varphi(p) = p-1$ y hay $p-1$ clases no nulas. Así, $g$ es raíz primitiva módulo $p$ si y solo si $\{g^1, g^2, \ldots, g^{p-1}\} = \{1, 2, \ldots, p-1\}$ como conjuntos módulo $p$. En otras palabras, $g$ genera el grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^*$.

Teorema de existencia de raíces primitivas

El teorema fundamental es: **existe una raíz primitiva módulo $n$ si y solo si $n \in \{1, 2, 4, p^k, 2p^k\}$** para algún primo impar $p$ y $k \ge 1$.

El caso más importante para olimpiadas es $n = p$ primo: siempre existe una raíz primitiva módulo $p$. La demostración usa el hecho de que el polinomio $x^d - 1$ tiene a lo sumo $d$ raíces en $\mathbb{Z}/p\mathbb{Z}$ (un campo). Si el grupo $(\mathbb{Z}/p\mathbb{Z})^*$ no tuviera un elemento de orden $p-1$, el exponente del grupo sería un divisor propio $e < p-1$, y todos los $p-1$ elementos satisfarían $x^e \equiv 1 \pmod p$. Pero $x^e - 1$ tiene a lo sumo $e < p-1$ raíces, contradicción.

Para $n = p^k$ con $p$ impar: si $g$ es raíz primitiva módulo $p$, existe un levantamiento $g$ o $g + p$ que es raíz primitiva módulo $p^k$. El argumento usa el Lema de Hensel (o una variante directa con la fórmula del orden en potencias de primos).

Para $n = 2$: $\varphi(2)=1$ y $g=1$ es trivialmente raíz primitiva. Para $n=4$: $g=3$ tiene $\text{ord}_4(3)=2=\varphi(4)$. Para $n=2^k$ con $k \ge 3$: NO existen raíces primitivas; el grupo $(\mathbb{Z}/2^k\mathbb{Z})^*$ es isomorfo a $\mathbb{Z}/2 \times \mathbb{Z}/2^{k-2}$, que no es cíclico.

Cuántas raíces primitivas hay

Dado que existen raíces primitivas módulo $p$, ¿cuántas hay? La respuesta es exactamente $\varphi(p-1)$.

Demostración. Sea $g$ una raíz primitiva fija. Todo elemento de $(\mathbb{Z}/p\mathbb{Z})^*$ es de la forma $g^k$ para algún $k \in \{1,\ldots,p-1\}$. Por la fórmula del orden de una potencia, $\text{ord}_p(g^k) = (p-1)/\gcd(p-1, k)$. Esto es igual a $p-1$ si y solo si $\gcd(p-1, k) = 1$. El número de $k \in \{1, \ldots, p-1\}$ con $\gcd(p-1,k)=1$ es exactamente $\varphi(p-1)$.

Por ejemplo, módulo $7$ (donde $p-1=6$ y $\varphi(6)=2$): hay exactamente $2$ raíces primitivas. Verificamos: $3$ tiene orden $6$ (raíz primitiva); $3^5 = 243 \equiv 5 \pmod 7$ también tiene orden $6$ (otra raíz primitiva). Las demás potencias $3^2\equiv 2$ (orden 3), $3^3 \equiv 6$ (orden 2), $3^4 \equiv 4$ (orden 3), $3^6 \equiv 1$ (orden 1) no son raíces primitivas.

El índice: logaritmo discreto

Fijada una raíz primitiva $g$ módulo $p$, todo $a$ con $\gcd(a,p)=1$ se escribe de manera única como $a \equiv g^k \pmod p$ para algún $k \in \{1, \ldots, p-1\}$. Este exponente $k$ se llama el índice de $a$ en base $g$ módulo $p$, denotado $\text{ind}_g(a)$ o $\log_g a$.

El índice se comporta como un logaritmo: $\text{ind}_g(ab) \equiv \text{ind}_g(a) + \text{ind}_g(b) \pmod{p-1}$ y $\text{ind}_g(a^k) \equiv k \cdot \text{ind}_g(a) \pmod{p-1}$. Esto convierte multiplicaciones modulares en sumas, y potencias en multiplicaciones —exactamente como los logaritmos convierten problemas multiplicativos en aditivos.

Aplicación: resolver $x^5 \equiv 3 \pmod 7$. Con $g=3$: $\text{ind}_3(3)=1$. La ecuación se convierte en $5 \cdot \text{ind}_3(x) \equiv 1 \pmod 6$. La ecuación lineal $5k \equiv 1 \pmod 6$ tiene solución $k \equiv 5 \pmod 6$ (ya que $5 \cdot 5 = 25 \equiv 1$). Entonces $x \equiv 3^5 = 243 \equiv 5 \pmod 7$. Verificación: $5^5 = 3125 = 446 \cdot 7 + 3 \equiv 3 \pmod 7$. Correcto.

Residuos cuadráticos y raíces primitivas

Una de las aplicaciones más elegantes de las raíces primitivas es la caracterización de los residuos cuadráticos módulo un primo impar $p$. Un entero $a$ con $p \nmid a$ es un residuo cuadrático módulo $p$ (i.e., $x^2 \equiv a \pmod p$ tiene solución) si y solo si $a^{(p-1)/2} \equiv 1 \pmod p$.

Con una raíz primitiva $g$: escribe $a = g^k$. Entonces $a^{(p-1)/2} = g^{k(p-1)/2}$. Como $g^{p-1} \equiv 1$, el valor de $g^{k(p-1)/2}$ es $1$ si $k(p-1)/2 \equiv 0 \pmod{p-1}$, es decir si $(p-1)/2 \mid k(p-1)/2$... simplificando, si $k$ es par. Si $k$ es impar, $g^{k(p-1)/2} = (g^{(p-1)/2})^k \equiv (-1)^k = -1 \pmod p$ (pues $g^{(p-1)/2} \equiv -1$: tiene orden 2 y el único elemento de orden 2 en $(\mathbb Z/p\mathbb Z)^*$ es $-1$).

Conclusión: exactamente la mitad de los elementos de $(\mathbb{Z}/p\mathbb{Z})^*$ son residuos cuadráticos (los $g^k$ con $k$ par), y la otra mitad son no-residuos (los $g^k$ con $k$ impar). Esto es el Criterio de Euler expresado en lenguaje de raíces primitivas.