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

  • $\begingroup$ What does "belong to $\;h\pmod {p^m}\;$" mean, anyway? $\endgroup$ – DonAntonio Dec 3 '13 at 14:09
  • $\begingroup$ 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? $\endgroup$ – universalset Dec 3 '13 at 14:20
  • $\begingroup$ @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 $\endgroup$ – walterudoing Dec 3 '13 at 14:33
  • $\begingroup$ @universalset the "r" is "g".... It's a typo, thx for pointing out $\endgroup$ – walterudoing Dec 3 '13 at 14:35
  • 1
    $\begingroup$ @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$". $\endgroup$ – universalset Dec 3 '13 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).

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