I'm looking for a proof of this that does not rely on the Chinese remainder theorem, since the exercise is from a book that has not reached such a point (Aluffi, Algebra).
Show that for $p$ prime, the multiplicative group $G=(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic. You may use that for $p$ prime, the equation $x^d=1$ has at most $d$ solutions in $\mathbb{Z}/p\mathbb{Z}$. (hint: for $g\in G$ of maximal order, $\forall h\in G, |h|\;|\;|g|$, and in particular, $h^{|g|}=1$.)
My only idea for now is constructing an element $a\in G$ such that $|a|=|G|$, using the fact that a group of order $n$ is cyclic $\iff\exists$ an element of order $n$.