# $m$th power residue, necessary and sufficient conditions.

Let $n$ be an integer for which $(\mathbb{Z}/n\mathbb{Z})^*$ is cyclic and $a$ is coprime to $n$. Given a positive integer $m$, find the necessary and sufficient conditions for $x^m \equiv a \pmod n$ to be solvable. Find the number of incongruent solutions modulo $n$ when it is possible.

I know that it is the $m$th power residue. I have found plenty of information online but I just needed some precise information.

First of all, when $\Bbb Z_n^*$ is cyclic, there exists an element $g$ such that $$\Bbb Z_n^* =\left\{g^{k}\big / 0\leq k< \varphi(n)\right\}=\left\{1,g^1,g^2,\cdots,g^{\varphi(n)-1}\right\}$$
and everything can be done using this hint! For example, $a=g^k$ is an $m$th power residue if and only if there exists an $i$ such that $x^m=(g^i)^m=a$, which happens if and only if $\varphi(n)$ divides $im-k$. This is equivalent to the condition that $k$ is divisible by $\gcd(\varphi(n),m)$, and hence the elements which are $m$th powers are exactly $$1, g^{\gcd(\varphi(n),m)}, g^{2\gcd(\varphi(n),m)}, \cdots$$