Find all primes which have exactly 8 primitive root 
Find all primes $p$ which have exactly 8 primitive roots $a$ modulo $p$, where $1\leq a\leq p-1$.

This is what I did so far: all primes $p$ have  a primitive root $a$. 
The other primitive roots are those elements of the form $a^i$, such that $\gcd(i,p-1)=1$.  
So, we want to find all $p$ such that $\phi(p-1)=8$.  
And here I'm stuck...
 A: Let's find all natural numbers $n$ such that $\phi(n)=8$, then we'll check which ones have the property that $n+1$ is a prime.
If the prime factorization of $n$ is $p_1^{a_1}\cdots p_r^{a_r}$, then
$$\phi(n)=\phi(p_1^{a_1})\cdots\phi(p_r^{a_r})=p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)\cdots p_r^{a_r}(p_r-1).$$
The prime factorization of $8$ is $2^3$. What are the possible ways these $2$'s can be distributed among the factors on the right side of this equation?
To break this down further:


*

*Which prime powers $p_i^{a_i-1}$ contribute nothing but powers of $2$ (and at most three of them)? (only when $p_i=2$ and $1\leq a_i\leq 4$, or $p_i$ is some other prime and $a_i=1$)

*Which primes $p_i$ have the property that $(p_i-1)$ contribute nothing but powers of $2$?
(only when $p_i=3$ or $p_i=5$)

A: In order for $\phi(n) = 2^k$ to occur, we need $n$ to be composed as $2^{k_0} \prod_i p_i$ where each $p_i$ is of the form $2^{k_i}+1$ (this all follows from the multiplicativity of $\phi$, see e.g. Wikipedia). In the present case, $k = 3$.
First, one observes that the largest prime of the desired form with $k_i \le 3$ is $5$; the other one is $3$. We can fill up the remaining parts with some factors $2$. This yields:
$$n = 15, 16, 20, 24, 30$$
as solutions for $p-1$. We conclude that $p = 17, 31$ are the only solutions.
A: Consider the factorisation of $p-1$ into primes :
$p-1=2^{b}p_1^{a_1}p_2^{a_2}\ldots p_r^{a_r}$.
Then $\phi(p-1)=2^{b-1}\prod_{k=1}^r \phi(p_k^{a_k})$, but $\phi(p_k^{a_k})=p_k^{a_k-1}(p_k-1)$. You deduce that $p_k-1$ must divide
$\phi(p-1)=8$, so $p_k-1$ must be one of $1,2,4$ or $8$, and so $p_k$
can only be $3$ or $5$.
So we can write :
$$
p-1=2^{e_2}3^{e_3}5^{e_5}
$$
Since $2$ is not a solution, $e_2>0$. So
$$
8=\phi(p-1)=2^{e_2-1}3^{\max(0,e_3-1)}\times 2 \times 5^{\max(0,e_5-1)} \times 4
$$
If $e_3=0,e_5=0$, then $8=2^{e_2-1}$, so $e_2=4$ and hence $p=17$.
If $e_3=0,e_5\gt 0$, then $8=2^{e_2-1}5^{e_5-1}\times 4$, so $p=21$ : not a prime.
If $e_3 \gt 0,e_5=0$, then $8=2^{e_2-1}3^{e_3-2}\times 2$, so $p=25$ : not a prime.
If $e_3 \gt 0,e_5 \gt 0$, then $8=2^{e_2-1}3^{e_3-2}5^{e_5-2}\times 2$, so $p=31$.
So there are exactly two solutions : $p=17$ and $p=31$. 
