Recursive relation of multiplicative orders for integers modulo a prime power

Question

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!

Answer 1

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

Answer 2

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.