1
$\begingroup$

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.

  • 0
    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.2012-06-10

3 Answers 3

3

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

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.\:$

  • 0
    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)2012-06-17
1

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