# Show that if $x$ is a primitive root modulo $p^r$, then $x$ is a primitive root modulo $p$ [duplicate]

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.

## marked as duplicate by lab bhattacharjee elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

• 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? – 伽罗瓦 May 14 '18 at 11:13
• 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. – G Tony Jacobs May 14 '18 at 11:17

## 1 Answer

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