Hay φ(φ(n)) raíces primitivas.
El concepto de contar raíces primitivas te sirve para saber cuántos generadores hay en el grupo multiplicativo de los enteros módulo $n$, que escribimos como $(\mathbb{Z}/n\mathbb{Z})^\times$. Una raíz primitiva módulo $n$ es un entero $g$ tal que, si tomas sus potencias, generas todos los enteros coprimos con $n$ módulo $n$. En el lenguaje de teoría de grupos, si $(\mathbb{Z}/n\mathbb{Z})^\times$ es un grupo cíclico, una raíz primitiva es simplemente un generador de este grupo. El resultado fundamental es que si un módulo $n$ tiene una raíz primitiva, entonces vas a encontrar exactamente $\phi(\phi(n))$ de estas raíces, donde $\phi$ es la función phi de Euler.
Esta técnica de conteo es clave en las olimpiadas de teoría de números para analizar cómo se estructuran los sistemas reducidos de residuos. Te permite calcular la probabilidad de que un elemento que elijas al azar sea un generador, y se usa mucho en problemas que traen aritmética de índices (logaritmos discretos) y el orden de los elementos. Entender este conteo te da una idea de qué tan densos son los generadores; por ejemplo, para un primo $p$, la densidad de raíces primitivas es $\phi(p-1)/(p-1)$.
La intuición detrás de la fórmula se basa en el isomorfismo entre un grupo cíclico de orden $