This question was proposed in an Elementary number theory textbook I own. The question stated for the conditions needed such that $x^x \equiv c\pmod p$, where $p$ is a prime. I'm really not sure how to begin. I went through several examples to get some intuition, but even in some pretty simple examples, I couldn't formulate any methods, I obtained solutions only through guesswork, at times, I wasn't even able to find any solutions. Perhaps it is needed to use FLT and order properties, but I haven't been able to follow through. Does there always exist a solution to $x^x \equiv c\pmod p$? How does one find the solution?
Any help/feedback is appreciated
Best Answer
Hint: By Fermat's little theorem, we have $$ \begin{cases} x \equiv a \pmod p\\ x \equiv b \pmod {p-1} \end{cases} \implies x^x \equiv a^b \pmod p $$ for any $a \neq 0$.
For any $c \not \equiv 0 \pmod p$, we can write $c \equiv a^b \pmod p$ for some $1 \leq a \leq p-1$ and $0 \leq b \leq p-1$. By the Chinese remainder theorem, we can necessarily find a number $x$ for which $x \equiv a \pmod p$ and $x \equiv b \pmod {p-1}$.
More specifically, if we take $x = pb - (1-p)a$, then we find that $$ x = pb - (1-p)a \equiv 0\cdot b - (-1) \cdot a \equiv a \pmod p\\ x = pb - (1-p)a \equiv 1 \cdot b - 0\cdot a \equiv b \pmod{p-1}. $$ Thus, we find that $x = pb - (1-p)a$ will satisfy $x^x \equiv c \pmod p$.