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


*

*Prove that $\mathbb{Z}_p$ has $2^{k-1}$ primitive roots.

*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?
 A: Hints: 


*

*Because p is a prime $\mathbb{Z_p^*}$ is cyclic so there exist an element of order $p-1=2^k$

*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}$


*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}$


A: Number Theoretic Proof


*

*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}$ 

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