Under what conditions is $x^x \equiv c\pmod p$? 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
 A: 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$.
A: Just expanding the answer of Ben Grossmann:
Fix $c$ and prime $p$.
If $c\equiv 0 \pmod{p}$ then take $x = p$.
Otherwise let $a$ be any generator of the multiplicative group $\mathbb{Z}_p^\star$ (it is well known that this group is cyclic, so it has a generator) and let $b\in\{0,\ldots,p-1\}$ be the discrete logarithm of $c \bmod p$ with the base $a$, i.e. $a^b\equiv c\pmod{p}$ ($b$ exists because $a$ is a generator).
Because $p$ and $p-1$ are relatively prime, by the Chinese Remainder Theorem there exists $x\in\{1,\ldots,p(p-1)\}$ such that $x\equiv a\pmod{p}$ and $x\equiv b\pmod{p-1}$, so $x = y\cdot(p-1)+b$ for some $y$.
We have
$$x^x\equiv a^{y(p-1)+b}\equiv a^b\equiv c\pmod{p}$$
because $a^{p-1}\equiv 1\pmod{p}$, by the FLT.
