# Prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$. [duplicate]

For an odd prime, prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$.

I have proved the other way round that any primitive root of $p^n$ is also a primitive root of $p$ but I have not been able to solve this one. I have tried the usual things that is I have assumed the contrary that there does not exist the primitive root following the above condition and then proceeded but couldn't solve it.

## 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(); } ); }); }); Dec 17 '15 at 16:31

• This is false when $p=2$, since there is a primitive root modulo $2^2=4$, but no primitive root modulo $2^n$ for $n \geq 3$. – Ivan Loh Mar 17 '13 at 13:14
• Sorry i have forgotten to mention that p is a odd prime. I have edited the question now – justice league Mar 17 '13 at 13:17

Let $g$ be a primitive root $\pmod{p^2}$. Then $p|(g^{p-1}-1)$ by Fermat's little theorem and $p^2 \nmid (g^{p-1}-1)$ since $g$ is a primitive root. Thus by Lifting the Exponent Lemma, $p^{n-1}\|((g^{p-1})^{p^{n-2}}-1)$ and $p^n\|((g^{p-1})^{p^{n-1}}-1)$, so $g$ is also a primitive root $\pmod{p^n}, n>1$.

Edit: More details: Let $d$ be the order of $g \pmod{p^n}, n>1$. Since $g$ is a primitive root $\pmod{p^2}$, we have $p(p-1) \mid d$. By above, $d|p^{n-1}(p-1), d\nmid p^{n-2}(p-1)$, so $d=p^{n-1}(p-1)$, and thus $g$ is a primitive root $\pmod{p^n}, n>1$.

• Thank You for answering and that link. I didn't know about that lemma. But shouldn't this be solvable by using more elementary methods ? – justice league Mar 17 '13 at 14:07
• Lifting the Exponent Lemma is proven by just binomial theorem and induction. It is elementary (well, elementary enough to be used for olympiad mathematics). Of course you can get around using this lemma; all you have to do is reproduce the proof for this special case, but I don't see the point. Any approach to this will probably end up using binomial theorem somewhere anyway. – Ivan Loh Mar 17 '13 at 14:47

We know from here, if $ord_pa=d, ord_{(p^2)}a= d$ or $pd$

If $a$ is a primitive root $\pmod {p^2}, ord_{(p^2)}a=\phi(p^2)=p(p-1)$

Then $ord_pa$ can be $p-1$ or $p(p-1)$

But as $ord_pa<p, ord_pa$ must be $p-1=\phi(p)\implies a$ is a primitive root $\pmod p$

Again from here, $$ord_{(p^s)}(a)=d, ord_{p^{(s+1)}}(a)=pd,\text{ then } ord_{p^{(s+2)}}(a)=p^2d$$

So, as $ord_pa=p-1,ord_{(p^2)}a=p(p-1); ord_{(p^3)}a$ will be $p\cdot p(p-1)=\phi(p^3)$

Again as, $ord_{(p^2)}a=p(p-1) ord_{(p^3)}a=p\cdot p(p-1);ord_{(p^4)}a$ will be $p\cdot p^2(p-1)=\phi(p^4)$

Let us give a more elementary answer, while still using some binomial theorem. But we shall employ no more than a binomial lemma. It states that, for a prime $p$, and an integer $1\leq a\leq p-1$, we have $p\mid \binom{p}{a}$.
Now you know that $a$ is a primitive root of $p^2$, so the order of $a$ modulo $p^2$ is $p(p-1)$. And we know that $a^{p-1}=1+kp$ for some $k$. Then the assumption that $a$ is a primitive root of $p^2$ implies that $k$ is not divisible by $p$. Therefore $$a^{p^n(p-1)}=(a^{p-1})^{p^n}=1+kp^{n+1}+mp^{n+2}$$ for some $m$.(This is the place where we make use of the binomial lemma.) This directly tells you that $a$ is a primitive root of $p^n$ for every $n\ge1$.

More Details. We elaborate upon two things: Firstly, we show the centered equation, and, secondly, we show how that implies the primitivity of $a$. For the first, use the lemma to deduce that $(a^{p-1})^{p}=1+kp\times p+\text{terms of higher powers of$p$}$. Now, by induction, the result follows. For the second, just divide $(a^{p-1})^{p^r}$ by $p^n$ for $k=0,1,\ldots,n-1$, to see that, for lower powers of $a$ than $(a^{p-1})^{p^{n-1}}$, it cannot be congruent to $1$ modulo $p^n$. So $a$ is indeed a primitive root of $p^n$.

If there is any error in the above proof, please inform me; if there is any ambiguity, please point it out, thanks.

• "For the first, use the mistake of freshmen to deduce that $(a^{p−1})^p=1+kp×p+\text{terms of higher powers of} p$" That holds by using binomial theorem, but it does not follow from freshman's mistake, since freshman's mistake only deals with $\pmod{p}$ and not higher powers of $p$. (P.S. I note that this is similar in spirit to the proof of Lifting the Exponent Lemma) – Ivan Loh Mar 18 '13 at 11:45
• I see now that the matter has nothing to do with the mistake of freshmen, and have edited the answer. Hope this helps in improving upon it. Thanks for pointing the error out. – awllower Mar 18 '13 at 13:00
• Looks good now (+1) – Ivan Loh Mar 18 '13 at 15:18