# 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? – DonAntonio Dec 3 '13 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? – universalset Dec 3 '13 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 – walterudoing Dec 3 '13 at 14:33
• @universalset the "r" is "g".... It's a typo, thx for pointing out – walterudoing Dec 3 '13 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$". – universalset Dec 3 '13 at 14:44

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}$. – walterudoing Dec 3 '13 at 14:55
• I understand that $p-1|g^{\phi(m)}$, but how does it relate to $p^r$? – walterudoing Dec 3 '13 at 14:58