Conjecture: Prove that, $\forall (m,n,k)\in\Bbb Z_{>0}^{3}$ there exists $x\in \Bbb Z_{>0}$, such that: $$m^x \equiv x^n\pmod k$$
The conjecture seems correct.
Also this conjecture is possible generalization of the known conjecture.
If $m=1$. Then the conjecture is trivial. We have $x^n-1\pmod n$. Then the smallest $x$ equals to $x=n+1$. Because, $x-1\mid x^n-1^n$.
The $n=1$ case has been proven before.
I tried to solve the general case using the induction, but the induction didn't worked.
But, I have many computational results.
I chose big prime numbers to check the conjecture.
Let $m=31$, $n=17, k=59$.
I don't have a software. I've experimented with Wolfram as much as I can. Here is the my input:
Table (31^x-x^17)/59 , x=1 to 100
I found that the smallest $x$ equals to $99$.
These are the things I can do.
There are lots of example where this is not true.
Given $p$ prime and $m\not\equiv 0\pmod p$ and $m^{p-1}\not\equiv 1\pmod{p^2},$ then $k=p^2, n=p$ has no solution.
This is because $m$ is a unit modulo $k,$ so $x$ cannot be a multiple of $p.$ But then $m^{x(p-1)}\equiv x^{p(p-1)}\equiv 1\pmod{p^2}.$ So $m$ must be of order a divisor of $x(p-1)$ and not of order $p-1.$ So we get $x$ must be a multiple of $p.$
So, for example, $m=3, k=4, n=2$ has no solution.
In general, if $\gcd(k,m\phi(k))=1,$ we easily get a solution by solving the Chinese remainder theorem problem:
$$x\equiv 1\pmod k\\x\equiv 0\pmod{\phi(k)}$$
Then $x=\phi(k)c=kd+1$ and $$m^x=(m^{\phi(k)})^{c}\equiv 1\equiv (dk+1)^n\pmod k$$
When $k=pq,$ where $p,q$ are primes and $p\mid q-1,$ we can find an $m\not\equiv 0\pmod p$ and $m$ is a multiplicative generator modulo $q,$ then $k=pq, n=p.$ Then if $m^{x}\equiv x^p\pmod{pq},$ $$m^{x(q-1)/p}\equiv x^{q-1}\equiv 1\pmod{pq}$$
So $x(q-1)/p$ must be a multiple of $q-1,$ and hence $x$ must be a multiple of $p,$ which is not possible because $m^x$ would be a unit modulo $pq$ but $x^p$ would not.
In particular, $k=2q$ where $q$ is an odd prime and $m$ is not a square modulo $q,$ then $$m^x\equiv x^2\pmod{2q}$$ has no solution.
For example, $m=5,k=6,n=2.$
More generally there is always a solution if $\gcd(\phi(k),k)=1.$
If $\gcd(\phi(k),k)=1,$ then $k$ is square-free.
Now, let $\gcd(m,k)= k_1$ and define $k_2=k/k_1,$ so $\gcd(k_1,k_2)=1$ since $k$ is square-free.
Then $\gcd(m,k_2)=1$ and $\gcd(\phi(k_2),k_2)=1.$ So by the above, there are an infinite set of solutions $x_r=x_0+\phi(k_2)k_2r$ to $m^x\equiv x^n\pmod{k_2}.$
But $\gcd(\phi(k_2)k_2,k_1)=1,$ so there are infinitely many $x_r$ divisible by $k_2.$ So for those $r,$ $$m^{x_r}\equiv 0\equiv x_r^{n}\pmod{k_1}\\m^{x_r}\equiv x_r^n\pmod{k_2}$$ so we have a solution for $(m,n,k).$
For example, when $(m,k,n)=(3,15,2)$ then $k_1=3,k_2=5,$ and we get $x_r=16+20r$ are solutions to $3^x\equiv x^2\pmod{k_2}.$
When $r\equiv 1\pmod{3}$ then $x_r$ is divisible by $k_1=3$ and thus we get $x_1=36$ is a solution to:
$$3^{36}\equiv 36^2\pmod{15}$$
There are smaller solutions, but this one works.