Proving that the multiplicative group mod p (p is prime) is cyclic Let $\mathbb{Z}_p^*$ be the group of integers $\{1,2,3,\dots,p-1\}$ under multiplication mod $p$, where $p$ is a prime.
Given the following two facts:


*

*If $d$ divides $p-1$, then there are exactly $d$ elements in  $\mathbb{Z}_p^*$ such that $a^d\equiv 1$.

*For all positive integer $n$, we have $\sum_{d | n} \phi(d) = n$. That is, the sum of Euler-Phi functions over divisors is $n$. (A proof can be found here https://proofwiki.org/wiki/Sum_of_Euler_Phi_Function_over_Divisors).
Given the above facts, how may we prove that the group  $\{1,2,3,\dots,p-1\}$ under multiplication mod $p$ is cyclic?
 A: Let $\psi(d)$ denote the number of elements of order $d$ in $\mathbb Z_p^*$.
Note that if $a\in\mathbb Z_p^*$ has order $d$, then $a^r$ has order $d$ if and only if $\gcd(r,d)=1$.
Thus are precisely $\phi(d)$ elements of the form of $a^r$ which have order $d$.
It follows that $\phi(d)$ divides $\psi(d)$ for all $d$.
Using (1) we want to show that $\psi(d)$ is either $0$ or equal to $\phi(d)$ for all $d|(p-1)$.
Assume on the contrary that there is some $d$ dividing $p-1$ such that $\psi(d)>\phi(d)$.
Let $a$ be an element of order $d$.
Out of the $d$ elements $a,a^2,\ldots,a^d$, precisely $\phi(d)$ have order $d$.
By our assumption, there is an element $b$ of order $d$ which is not equal to any of the $a^i$'s.
But note that $b$ and each $a^i$ satisfies $x^d\equiv 1\pmod{p}$.
This means that the congruence $x^d\equiv 1\pmod{p}$ has more than $d$ solutions, contrary to (1).
So we have $\psi(d)=0$ or $\phi(d)$.
Now note that $\sum_{d|(p-1)}\psi(d)=p-1$.
This is because each element of $\mathbb Z_p^*$ has order $d$ for some $d|p-1$. 
From our earlier inference we also have $\sum_{d|p-1}\psi(d)\leq \sum_{d|p-1}\phi(d)$.
The RHS is equal $p-1$ by (2).
Therefore we cannot have $\psi(d)=0$ for any $d|p-1$ and hence $\psi(p-1)>0$, proving there is an element of order $p-1$ (and hence precisely $\phi(p-1)$ such elements).
