Let $p$ be an odd prime and $a \not \equiv 1 \pmod p$. Show that the order of $a$ modulo $p^m$ divides $p^m - p^{m-1}$.
If the order of $a$ modulo $p^m$ exists, then we must have $\gcd(a,p^m)=1$. This means we can use Euler's Theorem
$$ a^{\phi(p^m)} \equiv a^{p^m - p^{m-1}} \equiv 1 \pmod {p^m} $$
The order is the smallest $j$ such that $a^j \equiv 1 \pmod {p^m}$, and so the order divides $p^m - p^{m-1}$.