$r$ is a primitive root of odd prime $p$ and $a\not\equiv 0\pmod{p}$. Find the number of solutions to the congruence $$xr^x\equiv a\pmod{p}$$

Here is my attempt :
Since $r$ is a primitive root, there exists $k$ such that $x\equiv r^k\pmod{p}$. Therefore the congruence becomes $$r^kr^{r^k}\equiv a \pmod{p}\\r^{r^k+k}\equiv a \pmod{p}$$

I don't know where to go from here. Any help? Thanks!

  • 1
    $\begingroup$ Try writing $a$ as a power of $r$, and note that you can reduce the exponent mod $p-1$ (not mod $p$, so you can't put $r^k$ in the exponent). $\endgroup$ – Nishant Apr 2 '15 at 16:18
  • $\begingroup$ Ahh that looks neat... do I get $r^k+k\equiv \text{ind}_r a \pmod{p-1}$ ? How to conclude about the number of solutions from here ? $\endgroup$ – rrr Apr 2 '15 at 16:20
  • $\begingroup$ While the problem statement isn't clear (in fact, I'd call it actively misleading), yes, you should certainly look at $x$ modulo $p(p-1)$. $\endgroup$ – Greg Martin Apr 2 '15 at 16:32
  • $\begingroup$ which part isn't clear/misleading @GregMartin ? this is related to discrete lambert problem if it helps.. $\endgroup$ – rrr Apr 2 '15 at 17:02
  • $\begingroup$ What does $\text{ind}_r$ mean? $\endgroup$ – Nishant Apr 2 '15 at 18:45

Your Answer

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

Browse other questions tagged or ask your own question.