# Number of solutions of $x^e \equiv c \mod p$

We have to find the number of solutions to the equation:- $$x^e \equiv c \mod p$$ where $$c \not\equiv 0\mod p$$. For $$c=1$$, we can prove that the above has $$\gcd(e,p-1)=d$$ solutions in the following way:-

Assume that $$g$$ is a primitive root of $$p$$. Hence there exists $$0 such that $$g^k \equiv x\mod p \implies g^{ke} \equiv 1\mod p \implies (p-1)|ke$$ Let $$d=\gcd(e,p-1)$$. Therefore $$\left(\frac{p-1}d\right) \mid k \cdot\left(\frac ed \right)$$. Now, we know that $$\gcd \left(\frac{p-1}d, \frac ed \right)=1$$. Therefore $$\frac{p-1}d$$ must divide $$k$$. Therefore $$k \in \left\{\frac{p-1}d, 2\left(\frac{p-1}d\right), \cdots,d\left(\frac{p-1}d\right)\right\}$$, (since $$0). Hence for $$c=1$$, there are $$d$$ solutions.

Now, I am asked to show that if a solution to $$x^e \equiv c\mod p$$ exists, then there must be $$d$$ unique solutions to the equation. I have shown that a solution exists iff $$c=g^{dn}\mod p$$, where $$d=\gcd(e,p-1)$$ and $$n \in \{1,2,\cdots,p-1\}$$. For this general equation, we must solve the follwing equation and show that it has $$d$$ unique solutions:-

$$ke \equiv nd \mod p-1 \implies k\left(\frac ed\right) \equiv n \mod \frac{p-1}d$$ How do I show that this has exactly $$d$$ unique solutions?

Suppose that $$x^e \equiv c \pmod p$$ has a solution, say $$x \equiv a$$. If $$b$$ is any solution, you can find some $$r$$ such that $$ar \equiv b$$. Then it follows that $$(ar)^e \equiv c \equiv a^e \pmod p.$$ Canceling $$a^e$$, we find that $$r^e \equiv 1 \pmod p.$$ So $$r$$ must be one of the $$d$$ solutions to $$x^e \equiv 1$$.
Conversely, you can see that if $$r^e \equiv 1$$, then $$(ar)^e \equiv c$$. Hence the solutions to $$x^e \equiv c$$ are the values $$ar$$ for each of the $$d$$ possible values of $$r$$.