Solo para 1, 2, 4, p^k y 2p^k.
Saber si existen raíces primitivas es una pregunta fundamental en teoría de números sobre la estructura del grupo multiplicativo de enteros módulo $n$, que escribes como $(\mathbb{Z}/n\mathbb{Z})^\times$. Una raíz primitiva módulo $n$ es un entero $g$ tal que las potencias de $g$ generan todos los enteros coprimos con $n$ módulo $n$. En términos de teoría de grupos, hay una raíz primitiva si y solo si $(\mathbb{Z}/n\mathbb{Z})^\times$ es un grupo cíclico. Cuando hay una raíz primitiva $g$, su orden multiplicativo es exactamente $\phi(n)$ (la función de Euler), y puedes escribir cada elemento $a$ coprimo con $n$ de forma única como $g^k \pmod n$ para algún índice $k$.
Este concepto es clave para simplificar la aritmética multiplicativa módulo $n$. Si hay una raíz primitiva, la multiplicación módulo $n$ se convierte en suma módulo $\phi(n)$ usando el logaritmo discreto (índice), de forma parecida a cómo los logaritmos reales transforman la multiplicación en suma. Esta propiedad estructural sirve muchísimo en criptografía (Diffie-Hellman, ElGamal) y para resolver congruencias de grados mayores de la forma $x^k \equiv a \pmod n$.
Sin embargo, las raíces primitivas no existen para todos los módulos. El Teorema de la Raíz Primitiva clasifica