# 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...

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.

• how about $p=17?$ Commented Mar 29, 2013 at 10:08
• Absolutely right, thanks. When going down the possibilities, it's apparently all too easy to forget $2^{k+1}$. Commented Mar 29, 2013 at 10:10

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$)

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$.

• why can not $e_2,e_3$ or $e_5$ be individually $0?$ For example, $p-1=2^{e_2}\implies e_2=4,p=17$ Commented Mar 29, 2013 at 9:59
• Thanks. What about p=17 ->p-1=16=2^4. ->phi(2^4)=2^3=8 ? Commented Mar 29, 2013 at 10:11
• @labbhattacharjee : corrected, thanks. Commented Mar 29, 2013 at 10:14