Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r. Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r.
I know if $g^k \equiv a\pmod{p}$, then $g^k \equiv a\pmod{p^m}$, but how can i get $h=(p-1)p^r$?
 A: We can prove something more generic.
Using this, if ord$\displaystyle _{p^s}a=d,$  ord$\displaystyle _{p^{s+1}}a=d$ or $p\cdot d$ where $p$ is odd prime and ord$_na$ is the multiplicative order of $a\pmod n$
A: You want to show that, for $g$ a primitive root modulo $p$, the order of $g$ modulo $p^m$ is of the form $(p-1)p^r$ for some $r$. Here are hints for two approaches:
(1) Prove that if $g$ has order $k$ modulo $p^m$, then it has either order $k$ or order $pk$ modulo $p^{m+1}$ (perhaps by writing out $g^k$ modulo $p^{m+1}$ and using the binomial theorem).  Now use induction on $m$ to get your result.
(2) Show that the order of $g$ modulo $p^m$ is divisible by $p-1$ and then observe that it must divide $(p-1)p^{m-1}$ by Lagrange's theorem (or your favorite specialization thereof).
A: Let $g \in \Bbb Z^{+}$ without loss of generality. If $g$ is a primitive root modulo $p$, then $(g,p)=1$. Hence $(g, p^{m})=1$. Suppose $g$ belongs to $h$ modulo $p^{m}$, where $h \in \Bbb Z^{+}$. Hence $g^{h} \equiv 1 \text{ (mod } p^{m})$. It follows that $p^{m}|g^{h}-1$.  Hence 
$$\; \; p^{m}q=p(p^{m-1}q)$$
$$=pq'$$
$$\quad \; \; \, =g^{h}-1 \text{},$$
where $q,q'\in \Bbb Z^{+}$. Hence $g^{h} \equiv  1 \text{ (mod } p)$. But $g$ is a primitive root modulo $p$. Thus $\phi(p)|h$, or
$$h=\phi(p)s$$
$$\qquad \, =(p-1)s \text{,}$$
where $s \in \Bbb Z^{+}$. Note
$$h| \phi(p^{m}) \text{,}$$
or equivalently, $h|p^{m-1}(p-1)$. Hence 
$$p^{m-1}(p-1)=ht \qquad\text{ (}t \in \Bbb Z^{+} \text{)}$$
$$\qquad \; \; =(p-1)st \text{.}$$
It follows that $p^{m-1}=st$. As the only positive divisors of $p^{m-1}$ are $1,p,p^{2},...,p^{m-1}$, we have $$s,t \in \{1,p,p^{2},...,p^{m-1}\} \text{.}$$
Let $s=p^{r}$ $(0 \le r \le m-1)$ to complete the proof.
