Is there always a solution $x$ to $x^x$ $=$ $a$ $\pmod p$ with $p$ prime?

Question

Is tnt following conjecture true:

There is always a solution $x$ to $x^x$ $=$ $a$ $\pmod p$ for any integer $a$ and prime $p$.

I was struggling with a problem recently to find the integer $x$ such that $x^x$ $=$ $a$ $\pmod p$ assuming my conjecture is true. For example, how would one easily solve $x^x$ $=$ $15$ $\pmod {59}$ not using brute force hopefully. Thanks.

Answer 1

If $\gcd(\varphi(n),n)=1$ and $a$ is any unit mod $n$ then solving the system

$$\begin{cases} x\equiv a \mod n \\ x\equiv 1 \mod \varphi(n)\end{cases} $$

for $x$ (using Sun-Zi aka CRT) then $x$ is a solution to $x^x\equiv a$ mod $n$.

Answer 2

We may assume $a$ coprime to $p$. Let $b$ be a primitive root mod $p$. Then $(b + kp)^{b+kp} \equiv b^{b+kp} \equiv b^{b+k} \equiv a \mod p$ for suitable $k$.