Prove $x^m\equiv a\pmod{p^k}$ have either $0$ solution or exactly $\gcd(m,\phi(p^k))$ solutions in $\mathbb{Z}_{p^k}$

Question

Let $a,m,k$ be integers. If $p$ is a prime such that $p\nmid a$. How to prove that $x^m\equiv a\pmod{p^k}$ has either $0$ solutions or exactly $\gcd (m,\varphi (p^k))$ solutions in $\mathbb{Z}_{p^k}$? I know that $ax\equiv c\pmod n$ has either $0$ solution or exactly $\gcd (n,a)$ solutions in $\mathbb{Z}_n$, but this doesn't seem useful here, any help would be appreciated.

Answer 1

(I will prove the equivalent claim that Rishi proposes in the comments.)

We will use the fact that there exists a primitive root $\color{blue}{g} \bmod p^k$ as long as $p\neq 2$ (as this latter case easily yields counterexamples). We then know that ${\color{blue}{g}}\,^{\color{red}a}\equiv 1\bmod p^k$ and ${\color{blue}{g}}\,^{\color{red}b}=x\bmod p^k$ for some positive integers ${\color{red}a},{\color{red}b}$ since $x$ and $1$ are relatively prime to $p$ by assumption. Hence ${\color{blue}{g}}\,^{\color{red}a}\equiv {\color{blue}{g}}\,^{{\color{red}b}m}\bmod p^k$, which implies that ${\color{red}a}\equiv {\color{red}b}m\bmod \varphi(p^k)$ as $\varphi(p^k)$ is the order of ${\color{blue}{g}} \bmod p^k$. And you know how to deal with this case.

(Have a look at this post by Bill Dubuque on modular order reduction for more information on the last step.)