How many solutions to the equation $C \equiv M^e \;(\mbox{mod}\;n)$?

Question

Fix $n,e\in \mathbb{Z}$ and let $C\in\mathbb{Z}_n$. How many solutions $M\in \mathbb{Z}_n$ do I have to the equation $$C \equiv M^e \;(\mbox{mod}\;n)\;?$$ This question arose from trying to solve the equation $$11\equiv M^7\;(\mbox{mod}\;187),$$ for $M<187. $

Answer 1

Let $G=Z_n$, $M \in G$ and $r = Ord_G(M)$. There are $r$ unique residues thus $r$ possible exponents $e$ for selected $M$. Note that $r \mid \lambda(n)$ where $\lambda(n)$ is the Charmichael lambda function on $n$. When $n\ \in \mathbb{P}$ (prime) then $\lambda(n) = \varphi(n)$ as it's a cyclic group generated by $\varphi(\varphi(n))$ generatos.