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?

  • 1
    $\begingroup$ 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$. $\endgroup$ – Derek Holt Mar 5 '15 at 22:44


  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}$
  • $\begingroup$ I haven't been able to proof the second hint. How would I do it? $\endgroup$ – Username Unknown Mar 9 '15 at 1:20
  • $\begingroup$ what about now is it clear $\endgroup$ – Elaqqad Mar 9 '15 at 9:39
  • $\begingroup$ I'm sorry for this answer which is not clear, but if there is something to improve just ask! $\endgroup$ – 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.

  • $\begingroup$ How do we know that the number of primitive roots is given by that formula? $\endgroup$ – Username Unknown Mar 9 '15 at 14:29
  • $\begingroup$ Have a look at this question: math.stackexchange.com/questions/166866/… $\endgroup$ – zed111 Mar 9 '15 at 16:11
  • $\begingroup$ 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. $\endgroup$ – Brandon Thomas Van Over Mar 11 '15 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.