# Let $p$ be a prime of the form $p=2^k+1$. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots.

Let $p$ be a prime of the form $p=2^k+1$.

1. Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots.
2. Let $g_0$ be a primitive root. Which powers of $g_0$ are primitive roots? Prove!

Since $p$ is a prime, then the order of the cyclic group $\mathbb{Z}_p$ is going to be $$\phi(p)=\phi(2^k+1)=2^k+1-1=2^k$$

Since $\mathbb{Z}_p$ is a group then there exist an identity element of order 1. We can say that there are $p-1$ elements whose order we do not know.

How do I continue with the proof?

• It is ${\mathbb Z}_p \setminus \{0\}$ that is cyclic of order $2^k$, not ${\mathbb Z}_p$. The primitive roots are the generators of that group. So you have to prove that a cyclic group of order $2^k$ has exactly $2^{k-1}$ generators; that is, $2^{k-1}$ elements of order $2^k$. – Derek Holt Mar 5 '15 at 22:44

## 2 Answers

Hints:

1. Because p is a prime $\mathbb{Z_p^*}$ is cyclic so there exist an element of order $p-1=2^k$
2. Consider any element $g_0$ of order $2^k$ so : $$\mathbb{Z_p^*}=\{1,g_0,\cdots,g_0^{2^k-1} \}$$ The elements of the form $g_0^i$ with $i$ is odd and $0\leq i\leq 2^k$ are primitive roots, when $i$ is even you can prove that $g_0^i$ is not a primitive root.

• if $i$ is odd , we want to prove that $g_0^i$ has order $2^k$. Let $m=ord(g_0^i)$ we have $$(g_0^i)^m=g_0^{mi}=1$$ but $g_0$ has order $2^k$, so $2^k$ divides $mi$, but $i$ is odd so $gcd(2^k,i)=1$ by Gauss's lemma $2^k$ divides $m$, hence $m=2^k$ (because by definition the order of any element is divides the order of the group $2^k$)
• If i is even write $i=2i'$ with $i'$ is integer so: $$(g_0^i)^{2^{k-1}}=((g_0)^{2^k})^{i'}=1^{i'}=1$$ thus $g_0^{i}$ is not a primitive root , because it's order is less than $2^{k-1}$
3. Conclude that there are exactly $2^{k-1}$ primitive roots.

• The number of primitive roots is exactly the number of odd powers which is $2^{k-1}$
• The number of non primitive roots are the number of even powers which is $2^{k-1}$
• I haven't been able to proof the second hint. How would I do it? – Username Unknown Mar 9 '15 at 1:20
• what about now is it clear – Elaqqad Mar 9 '15 at 9:39
• I'm sorry for this answer which is not clear, but if there is something to improve just ask! – Elaqqad Mar 10 '15 at 19:11

Number Theoretic Proof

1. Number of primitive roots of $n$ =$\phi(\phi(n))$. For $n=2^{k}+1$ (prime), this is $\phi(2^k) = 2^k-2^{k-1}=2^{k-1}$

2. Let $g_0$ be a primitive root. Then the order of $g_o^r$ is $\frac{o(g_0)}{gcd(r,o(g_0))}$. Hence $g_o^r$ is a primitive root when $gcd(r,o(g_0))$=1. Now $o(g_0)=2^k$, and $gcd(r,2^k)=1$ which means $r$ must be odd.

• How do we know that the number of primitive roots is given by that formula? – Username Unknown Mar 9 '15 at 14:29
• Have a look at this question: math.stackexchange.com/questions/166866/… – zed111 Mar 9 '15 at 16:11
• I would consider reading more about this in "Introduction to the theory of Numbers" in which they give a very nice proof of what values of p have primitive roots. – Brandon Thomas Van Over Mar 11 '15 at 8:48