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

Question

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?

Answer 1

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

Answer 2

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.