# Prove $\text{ord}(x,p^b) = p^{b-1} \cdot \text{ord}(x,p)$

Let $a=\text{ord}(x,m) :$ $a$ is the minimum value for which $x^a \equiv 1\pmod{m}$.

By inspection it appears that $$\text{ord}(x,p^b) = p^{b-1} \cdot \text{ord}(x,p)$$ where $x,p,b,$ belong to $\mathbb{Z}^+$, $x>1$, $p$ is odd prime.

1. Is this assertion actually true?
2. If so, what is a simple proof of it?

I may have a "proof" of my own, but even if it is correct (which I doubt) it seems much too complicated.

-
Note it is obviously not true if $x=1$, for example. What is true is that $o(x,p^b)=p^k o(x,p)$ for some $0\leq k < b$. – Thomas Andrews Jun 10 '12 at 18:48

This is not quite true. Take a primitive root $g$ mod $p$. If what you're saying was true, we'd have $ord(g,p^2) = p \cdot ord(g,p) = p(p-1)$, and $g$ would be a primitive root $g$ mod $p^2$. However, this is not true in general. What is true that either $g$ or $g+p$ is a primitive root $g$ mod $p^2$.

The smallest counter-example I've found along this line is $ord(14,29) = 28 = ord(14,29^2)$.

The smallest counter-example in general is $ord(3,11) = 5 = ord(3,11^2)$.

-

This is probably what you seek (T4.4 in William J. LeVeque, Fundamentals of Number Theory)

Suppose prime $\rm\:p\nmid a,\:$ and $\rm\:t =$ order of $\rm\:a\ (mod\ p).\:$ Suppose $\rm\:p^k\:|\:a^t\!-\!1\:$ but $\rm\:p^{k+1}\nmid a^t\! -\! 1.\:$ Then if $\rm\:p\! >\! 2\:$ or $\rm\:k\! >\! 1,\:$ the order of $\rm\:a\ (mod\ p^n)\:$ is $\rm\:t\:$ for $\rm\:n \le k,\:$ and $\rm\:t p^{n-k}$ for $\rm\:n \ge k.\:$

-
Mr Dubuque: I have gotten the book you recommended. I don't understand what the 'p-component' is. What is this double '||' mean? It looks like divide '|' but not quite. I understand p^k | a^t - 1 but not p^k || a^t - 1. – Nick Jun 17 '12 at 18:10
@Nick $\rm\:p^k\,||\,n\:$ means that $\rm\:k\:$ is the highest power of $\rm\:p\:$ dividing $\rm\:n,\:$ i.e. $\rm\:p^k\:|\:n\:$ but $\rm\:p^{k+1}\nmid n.\:$ That was LeVeque's wording. I've changed it to be clearer. – Bill Dubuque Jun 17 '12 at 23:46
No problem. You are clearly someone of exceptional knowledge and I am honored you would take time for someone like me (and the many others I am sure you have helped) – Nick Jun 17 '12 at 23:58

This isn't true as written because if $p=2$ then we have that $ord(3,2^4) = 4$ since $$3^4 \equiv 1 \pmod{16}$$ but $2^3 \cdot ord(3,2) = 8$ and $4 \neq 8$.

-