2
$\begingroup$

This question already has an answer here:

I'm trying to solve the following problem:

Let $p\geq 3$ be a prime number, let $r \in \Bbb N$, and let $x$ be a primitive root modulo $p^r$. Show that $x$ is a primitive root modulo $p$.


I'm pretty much out of ideas. I tried to use the following claim: $a$ is a primitive root modulo $n$ if and only if for every prime $q$ such that $q$ divides $\varphi(n)$ we have: $$a^{\frac{\varphi(n)}{q}}\not\equiv 1\pmod n$$

But got nothing.

$\endgroup$

marked as duplicate by lab bhattacharjee elementary-number-theory May 14 '18 at 11:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ I have a question regarding an idea of a proof but I'm not sure if it is correct. If we consider the power sequence of $a, \{1, a, \ldots \}$, in modulo $p$ then it clearly hits all the values in the unit group mod $p,$ $(\mathbb{Z}/p)^{x}$ as we can find a preimage for each element in modulo $p^r.$ So this means $a$ must be a generator modulo $p.$ Does this work? $\endgroup$ – 伽罗瓦 May 14 '18 at 11:13
  • 1
    $\begingroup$ The above comment seems correct, and a good deal easier than other approaches being discussed. Let $b$ be an element of $\{1,\ldots,p-1\}$. Then we have some power of $a$, say $a^n$, with $a^n\equiv b\pmod{p^r}$. This implies $a^n\equiv b\pmod{p}$, and we're good. $\endgroup$ – G Tony Jacobs May 14 '18 at 11:17
0
$\begingroup$

Hint: If $x^{\frac{p-1}{2}} \equiv 1 \bmod p$, then $x^{\frac{p-1}{2}(p^{r-1})} \equiv 1 \bmod p^r$ by induction on $r$.

$\endgroup$

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