# 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$?

• What does "belong to $\;h\pmod {p^m}\;$" mean, anyway? Dec 3, 2013 at 14:09
• I'm guessing that you mean $h$ to be the order of $g$ modulo $p^m$, and that the $r$ in your second line is no relation to the $r$ in your first line (though I'm not sure what it refers to). Could you clarify? Dec 3, 2013 at 14:20
• @DonAntonio it is defined that if h is the smallest positive integer such that $g^h\equiv1\pmod{p}$ we say g belongs to exponent h modulo p Dec 3, 2013 at 14:33
• @universalset the "r" is "g".... It's a typo, thx for pointing out Dec 3, 2013 at 14:35
• @walterudoing, so it looks like I was correcting in guessing that "belongs to exponent $h$ modulo $p$" is just another way of saying "has order $h$ modulo $p$". Dec 3, 2013 at 14:44

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$

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

• I'm not sure if I understand correctly...the problem says we have $g^{\phi{m}}\equiv 1\pmod{p}$, and we need to get $g^h\equiv 1\pmod{p^m}$. Dec 3, 2013 at 14:55
• I understand that $p-1|g^{\phi(m)}$, but how does it relate to $p^r$? Dec 3, 2013 at 14:58

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.