I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} \pmod {\varphi(p^k)}$ exists, then using Euler's theorem a solution is $$x \equiv a^q \pmod {p^k}$$ But how to compute $x$ if $q$ does not exist, i.e. if $\gcd(n,\varphi(p^k))\ne 1?$
An example would be $x^5 \equiv 6 \pmod{31}.\;$ Solving the similar $x^5 \equiv 6 \pmod{29}\;$ is easy: $x\equiv 6^{17}\equiv 13 \pmod{29}$
Are there practical algorithms without using primitive roots or the complete factorization of $p-1?$