Siempre existen para los números primos.
Una raíz primitiva módulo un primo $p$ es un entero $g$ tal que las potencias de $g$ generan todas las clases de residuos que no son cero módulo $p$. Para ser más exactos, el orden de $g$ módulo $p$ es $p-1$, que es el orden más grande que puede tener cualquier elemento en el grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^\times$. Esto significa que el grupo de unidades módulo $p$ es cíclico, y $g$ es un generador de este grupo. Cuando $g$ es una raíz primitiva, el conjunto ${g^1, g^2, \dots, g^{p-1}}$ es simplemente una permutación de ${1, 2, \dots, p-1}$ módulo $p$.
La idea de las raíces primitivas es fundamental en teoría de números porque te permite transformar problemas multiplicativos en aditivos, algo muy parecido a lo que hacen los logaritmos en el análisis real. Si escribes los números como potencias de una raíz primitiva (usando la idea del "índice" o "logaritmo discreto"), resolver congruencias de la forma $x^n \equiv a \pmod p$ pasa a ser una congruencia lineal en el exponente. Esta técnica te la vas a encontrar por todos lados en problemas de Olimpiada que tengan polinomios de grado alto módulo $p$, cálculos de orden y propiedades de los residuos.
Aunque las raíces primitivas existen para todos los