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.


1 Answer 1


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$$

How many elements are there?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.