Lo que hemos dicho hasta ahora es correcto, pero el hecho de que el grupo cíclico de orden $p-1$ es significativamente más difícil. Usted necesitará algo de idea real aquí; no es una cuestión de simplemente después de su nariz.
Un enfoque estándar es demostrar la Ciclicidad Criterio: un grupo de $G$ finito de orden $n$ es cíclico $\iff$ para cada divisor $d$ $n$ hay en la mayoría de las $d$ elementos $x$ $x^d = 1$ (el elemento de identidad). Generalmente esto se demostró mediante un conteo de argumento, y es útil saber que $\sum_{d \mid n} \varphi(d) = n$ donde $\varphi(d) = \# (\mathbb{Z}/d\mathbb{Z})^{\times}$ es el número de enteros $1 \leq e \leq d$$\gcd(e,d) = 1$.
Con eso en mano, debes observar que $\mathbb{Z}/p\mathbb{Z}$ es un campo, y por lo tanto el número de raíces del polinomio $x^d - 1 = 0$ es en la mayoría de las $d$. Este argumento termina mostrando un poco más: cualquier finito subgrupo del grupo multiplicativo de un campo es cíclico.
P. S.: Si te digo que el resultado es a menudo llamado "la existencia de raíces primitivas modulo $p$", que puede ayudar a que usted la busque en muchos de los textos introductorios sobre álgebra y/o la teoría de números.