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<k \le p-1$ 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<k\le p-1$). 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$.


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.