2
$\begingroup$

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

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

3 Answers 3

2
$\begingroup$

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$

$\endgroup$
0
1
$\begingroup$

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

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .