If $m=p^k$ is a prime power then I know:

$$\exists x\in \mathbb{Z}:x^n\equiv a\bmod p^k\iff a^{\frac{p-1}{\gcd(n,p-1)}}\equiv 1\bmod p^{j}$$ $$\text{ where: }j=\min\left(v_p(n)+1+[p\mid n][p=2],k\right)$$

Thus if I have the prime factorization of $m$ then by the Chinese remainder theorem I can just verify the above congruence holds for every prime power $p^{v_p(m)}$.

However what if I don't know the prime factorization of $m$?

Is there still a simple way to determine if $x^n\equiv a\bmod m$ is solvable?

What about just the special case when $n=2$ i.e. $x^2\equiv a\bmod m$ with $m$ composite?

4more comments