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.

Question

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

Answer 1

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

Answer 2

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$