Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For an odd prime $p$, prove that any primitive root $r$ of $p^n$ is also a primitive root of $p$

So I have assumed $r$ have order $k$ modulo $p$ , So $k|p-1$.Then if I am able to show that $p-1|k$ then I am done .But I haven't been able to show that.Can anybody help me this method?Any other type of prove is also welcomed.

share|cite|improve this question
Why does $p$ have to be odd? – Marc van Leeuwen Jul 14 '12 at 11:55
Look at Theorem 4.4 of – lab bhattacharjee Jul 14 '12 at 16:12
up vote 11 down vote accepted

For any $a$ relatively prime to $p^n$, there is an integer $k$ such that $r^k\equiv a \pmod{p^n}$ and hence such that $r^k \equiv a\pmod{p}$. Thus $r$ is a primitive root of $p$.

share|cite|improve this answer
+1 This explains that the statement is really obvious. In fact the argument is even shorter, the first part after "That means.." doesn't seem to state anything new – Marc van Leeuwen Jul 14 '12 at 11:54
@MarcvanLeeuwen: It started as very short. I added "that means $\dots$ and let r be $\dots$ for padding. – André Nicolas Jul 14 '12 at 13:11

Note that an integer $r$ with $\gcd(r,p)=1$ is a primitive root modulo $p^k$ when the smallest $b$ such that $r^b\equiv1\bmod p^k$ is $b=p^{k-1}(p-1)$.

Suppose that $r$ is not a primitive root modulo $p$, so there is some $b<p-1$ such that $r^b\equiv 1\bmod p$.

In other words, there is some integer $t$ such that $r^b=1+pt$.

Then of course we have that $p^{n-1}b<p^{n-1}(p-1)$, and $$r^{p^{n-1}b}\equiv 1\bmod p^n$$ because of

the binomial theorem.

(mouse over to reveal spoilers)

share|cite|improve this answer

$\begin{eqnarray}{\bf Hint}\quad\ \rm a\ \ is\ \ coprime\ \ to\ \ {\bf\color{#C00}p}\ \ &\Rightarrow&\rm\quad a\ \ is\ \ coprime\ \ to\ \ {\bf\color{#0A0}{p^n}}\\ & & \qquad\qquad \Downarrow\\ \rm r^k\equiv a\ \ (mod\,\ {\bf\color{#C00}p})\ &\Leftarrow&\rm\ \ \exists\,k\!:\ r^k\equiv a\ \ (mod\,\ {\bf\color{#0A0}{p^n}}) \end{eqnarray}$

share|cite|improve this answer

Exercise: If $X$ is a generating set for a group $G$ and $\phi:G\to H$ a homomorphism, then $\phi(X)$ is a generating set for the image of $G$ under $\phi$; in particular this means that if $\phi$ is surjective/onto then $\phi(X)$ is a generating set for $H$.

Now consider $G=(\Bbb Z/p^n\Bbb Z)^\times$ and $H=(\Bbb Z/p\Bbb Z)^\times$ with $\phi$ the mod $p$ map (see that it's well-defined and onto!) with a singleton generating set $X=\{a\}$ for $G$.

share|cite|improve this answer

If r is a primitive root of prime p, we can show that either r is a primitive root of $p^2$ or (r+c.p) is a primitive root of $p^2$ where (c,p)=1.

We can also show that if g is a primitive root of both p and $p^2$, it is also a primitive root of $p^k$ where k is a natural number.

Clearly, there exists one r+c.p where p|c or (c,p)=1 which is a primitive root of both p and $p^2$ =>r+c.p is a primitive root of $p^k$ where k is a natural number.

Each of $\phi(p-1)$ primitive root of p, will have associated (p-1) primitive roots which are congruent(mod p), but in-congruent(mod $p^2$) of $p^2$, p(p-1) primitive roots of $p^3$ and $p^{k-2}(p-1)$ primitive roots of $p^k$ where k≥3.

Each primitive root of $p^k$ will be associated to p primitive roots of $p^{k+1}$ where k > 1.

share|cite|improve this answer

Using this, if $ord_{(p^k)}a = d$ where k is a natural number, we can show that $ord_{(p^{k+1})}a = d$ or $pd$

Now, if r is a primitive root of $p^{k+1} => ord_{(p^{k+1})}a = \phi(p^{k+1})=p^k(p-1)$

=>$ ord_{(p^{k})}a = p^k(p-1)\ or\ p^{k-1}(p-1) $

=>But, $ ord_{(p^{k})}a ≤\ \phi(p^k) =p^{k-1}(p-1)$

=>$ ord_{(p^{k})}a = p^{k-1}(p-1)=\phi(p^k) $ => r is a primitive root of $p^k$ for all natural number k≥1

share|cite|improve this answer
Excuse me, can you explain more about why $ord_{(p^{k+1})}a = pd$? Thanks. – puresky Dec 12 '12 at 14:52
@puresky, please find the rectified answer.Thanks for your observation. – lab bhattacharjee Dec 12 '12 at 14:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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