10
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +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 $\endgroup$ – Marc van Leeuwen Jul 14 '12 at 11:54
  • $\begingroup$ @MarcvanLeeuwen: It started as very short. I added "that means $\dots$ and let r be $\dots$ for padding. $\endgroup$ – André Nicolas Jul 14 '12 at 13:11
13
$\begingroup$

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)

$\endgroup$
8
$\begingroup$

$\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}$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

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.