# Recursive relation of multiplicative orders for integers modulo a prime power

I was recently fiddling around with multiplicative orders of elements in $(\mathbb{Z} / p^k\mathbb{Z})^\times$ (p odd), and found that they seem to satisfy the property that

$O_{p^k}(n) = pO_{p^{k-1}}(n)$,  for $k>1$.

where $O_{p^k}(n)$ is the multiplicative order of $n$ modulo $p^k$, that is, the smallest $r>0$ such that $n^r \equiv 1 \mod p^k$.

My question comprises two parts:

1) Is this true? It seems like it probably is, there's a certain pleasing symmetry to it, and I couldn't find any small counter examples

2) If it's true, how would one go about proving it? I thought maybe by constructing a homomorphism $\theta:(\mathbb{Z} / p^{k-1}\mathbb{Z})^\times \to (\mathbb{Z} / p^k\mathbb{Z})^\times$, where $\theta(n) = n^p$, I could use the order-preserving property of $\theta$ to get that $O_{p^k}(n^p) = O_{p^{k-1}}(n)$, then use that to get that the LHS of the desired relation divides the RHS. After that, maybe another homomorphism in reverse to get the other division?

However, $\theta$ is only order-preserving if it is injective, which I've run into trouble proving (and suspect is, in fact, equivalent to the original statement) So, any ideas on how to prove $\theta$ is injective are welcome, as well as any other methods an undergraduate will understand that prove the relation. If it's true.

And if it's not true, any books with material covering why this relation appears to hold are also very welcome.

Thanks!

• I understand what you're getting at, as $\phi(p^k)=p\phi(p^{k-1})$, but this isn't necessarily the order of an element of $(\mathbb{Z} / p^k\mathbb{Z})^\times$. For example, the order of 2 in $(\mathbb{Z} / p^k\mathbb{Z})^\times$ is 3, not 6. Am I missing something? (edit: paren, $) Apr 3, 2017 at 18:35 • You are right, the element order is only a divisor of the group order, but still this information is useful. Did you try some examples? Apr 3, 2017 at 18:39 • I'm not completely sure what you mean. I've looked at multiple examples of these kinds of groups (though they obviously get a bit cumbersome to do on paper when you get to k large enough), I think I'm just missing a bit of insight about the structure of these types of groups. I can't work out why knowing that the order divides the value of Euler's totient helps. Why couldn't the order of 2 in$(\mathbb{Z} / p^k\mathbb{Z})^\times$just be 3 for all k? (edit: can't seem to edit the previous comment, that k in the 2nd occurrence of z/p^kz shouldn't be there, and the p should be a 7. sorry!!) Apr 3, 2017 at 18:53 ## 2 Answers Injectivity of$\theta$is equivalent to the claim $$x^p \equiv 1 \pmod {p^k} \implies x \equiv 1 \pmod {p^{k-1}}.$$ (We need the reverse implication to hold for$\theta$to be a homomorphism, and it does, which isn't hard to see.) We'll prove this by induction on$k$, starting with$k=2$. If we know$x^p \equiv 1 \pmod{p^2}$, in particular$x^p \equiv 1 \pmod p$, but we know that$x^p \equiv x \pmod p$for all$x$. Therefore$x \equiv 1 \pmod p$, and the base case holds. Suppose that the claim holds for$k$, and that$x^p \equiv 1 \pmod {p^{k+1}}$. In particular,$x^p \equiv 1 \pmod {p^k}$, so by the inductive hypothesis$x \equiv 1 \pmod {p^{k-1}}$. As a result,$x \equiv 1 + Cp^{k-1} \pmod {p^{k+1}}$. But raising this to the$p^{\text{th}}$power gives $$x^p \equiv 1 + \binom p1 C p^{k-1} + \binom p2 C^2 p^{2k-2} + \dotsb \equiv 1 + C p^k \pmod{p^{k+1}},$$ since$\binom p2 p^{2k-2}$is divisible by$p^{2k-1} \ge p^{k+1}$, so it and all following terms cancel. We must have$x^p \equiv 1 \pmod{p^{k+1}}$, which means$C \equiv 0 \pmod p$, and$x \equiv 1 + Cp^{k-1} \pmod {p^{k+1}}$implies that$x \equiv 1 \pmod {p^k}$. It's not always true that multiplicative orders multiply the way you want them to. For a probably-not-minimal counterexample, we have$O_{29}(14) = O_{29^2}(14) = 28$. The lemma does tell us that $$O_{p^{k+1}}(x) = p \cdot O_{p^k}(x)$$ holds as soon as$p \mid O_{p^k}(x)$. To see this, let$O_{p^k}(x) = p^i q$, where$q \mid p-1$and$0 < i < k$. • On one hand, if$x^{p^i q} \equiv 1 \pmod{p^k}$, then$x^{p^{i+1}q} \equiv 1 \pmod{p^{k+1}}$, so$O_{p^{k+1}}(x) \le p \cdot O_{p^k}(x)$. • On the other hand, if$x^{p^j r} \equiv 1 \pmod {p^{k+1}}$, then$x^{p^j r} \equiv 1 \pmod{p^k}$, proving that$j \ge i > 0$. So by the lemma it's true that$x^{p^{j-1} r} \equiv 1 \pmod{p^k}$, so$p^{j-1} r \ge p^i q$and$p^j r \ge p^{i+1}q$, proving that$O_{p^{k+1}}(x) \ge p \cdot O_{p^k}(x)$. • @ribbcastle For some other examples,$O_{11}(3)=O_{11^2}(3)=5$;$O_{113}(68)=O_{113^2}(68)=O_{113^3}(68)=112$Feb 24 at 5:52 • A question: is it for every prime$p$and every$1<a<p$the case that$O_p(a)=O_{p^2}(a)=\cdots=O_{p^{k-1}}(a)$and$O_{p^k}(a)=pO_{p^{k-1}}(a)$for some$k$? Feb 27 at 4:48 • True for at least the first 100 primes by a computer search. Feb 27 at 5:22 • I am now checking further, currently reached the 1700th prime. So far the only case with$O_{p^3}(a)$not divisible by$p$is that one with$p=113$,$a=68$. Feb 27 at 7:22 • I wonder if this somehow can be handled by considering the period of the$p$imal expansion for$1/(1-a)\$... Feb 27 at 7:30

We do have the almost as pleasing property $$O_{p^k} (a) = O_{p^{k-1}} (a) \text{ or } p \cdot O_{p^{k-1}}(a)$$

that lets us easily compute $$O_{p^k}(a)$$ recursively in terms of lesser prime powers until we reach base case $$O_p(a)$$ (then we use the factorization of $$p-1$$).

Using similar reasoning as Misha Lavrov's answer:

$$a^{O_{p^k}(a)} \equiv 1 \mod p^k \implies a^{O_{p^k}(a)} \equiv 1 \mod p^{k-1}$$ so $$O_{p^{k-1}}(a) \mid O_{p^k}(a)$$.

On the other hand, $$a^{O_{p^{k-1}}(a)} \equiv 1 \mod p^{k-1} \implies a^{O_{p^{k-1}}(a)} \equiv 1 + C p^{k-1} \mod p^k$$ $$\implies \left(a^{O_{p^{k-1}}(a)}\right)^p \equiv (1 + C p^{k-1})^p \equiv 1 \mod p^k$$ by the binomial theorem as all terms other than $$1^p$$ are divisible by $$p^k$$ (similar to freshman's dream).

Therefore $$O_{p^k}(a) \mid p \cdot O_{p^{k-1}}(a)$$.

Taking these two results together, $$O_{p^{k-1}}(a) \mid O_{p^k}(a) \mid p \cdot O_{p^{k-1}}(a)$$, we get our property.