Conjecture: There always exist $k\in \Bbb N$, such that $m^k\equiv k\pmod n$, where $m,n\in\Bbb N.$ Conjecture:

Let $m,n\in\Bbb N$. Then there always exists $k\in \Bbb N$, such that $m^k\equiv k\pmod n$ holds.

This question comes from here.

Let $m,n\in\Bbb Z_{>0}$ are fixed numbers, such that $$m^{k_0}-k_0\equiv 0\pmod n$$ for some $k_0\in \Bbb N$.
Then, there exist infinitely many $k$, such that $$m^k-k\equiv 0\pmod n.$$

We proved that, if there exist such $k$, then there exist infinitely many $k$.

But here, the question is: Does there always exist the smallest $k$?

Numerical results support the conjecture. The question seems beyond of my elementary knowledge, so I don't have a non-trivial attempt, unfortunately.
 A: This is a special case of the following fact:
Claim: Let $a,b,c$ be positive integers. Then there are infinitely many positive integers $x$ so that
$$a^x-x\equiv b\pmod c$$
This claim is similar to the following olympiad problem: Brazil MO 2005/6,
in which $a^x-x$ is replaced by $a^x+x$. The link also contains a proof of that problem (in post #7). That proof works identically for this too. I'll sketch it for completeness.
We will prove the claim by induction on $c$, with base case $c=1$ trivial.
Now assume $c>1$. First, notice that the sequence $a, a^2, \dots$ is eventually periodic modulo $c$, say with period $\ell$. Let $d=\gcd(c,\ell)$.
We want to show that $d<c$. If not, we have $\ell=c$, which implies the sequence $a^i$ contains every residue mod $c$, so some power of $a$ is divisible by $c$, but in this case $\ell=1$ (the sequence is eventually constant).

Thus $d<c$. Then by the induction hypothesis, for every $0\leq i<d$ there is a large positive integer $n_i$ for which
$$a^{n_i}-n_i\equiv i \pmod d$$
By "large" I mean bigger than the last $i$ for which $a^i\not\equiv a^{i+\ell}\pmod c$.
Let $b=qd+r$, where $0\leq r<d$. Then we have
$$a^{n_r}-n_r=r+md$$
for some integer $m$. Because $n_r$ is large, we can write for any positive $y$:
$$a^{n_r+y\ell}-(n_r+y\ell)\equiv a^{n_r}-n_r-y\ell\equiv r+md-y\ell\pmod c$$
As $d=\gcd(c, \ell)$, we can find integers $A, B$ so that $Ac+B\ell=d$. Then picking $y\equiv mB\pmod c$ we get $a^x-x\equiv r\pmod c$ for $x=n_r+y\ell$, which finishes the proof.
A: Here is a proof by strong induction on $n$ with $m$ fixed. In it I utilize your result that once such solution $k$ exists, then there are infinitely many solutions.
Base case:
Let $n=1$, then any $k$ works as $1$ is divisor of any integer.
Induction step:
Let $n>1$, and assume solution exists for all $i<n$. Let's write
$$n=ab,\gcd(a,m)=1,b \mid m^t$$
where $t$ is some sufficiently large positive integer.
This is just partitioning of prime factors of $n$ based on whether they divide $m$ or not. Now since $n>1$, we have $\varphi(a)\leq \varphi(n) <n$, and by the induction hypothesis there is $l$ such that
$$m^l\equiv l \pmod{\varphi(a)}.\tag{*}$$
By your result we know that since such solution exists, then infinitely many solutions exist. So choose $l$ such that $l\geq t$. Then $b\mid m^l$. Let $k=m^l$, we now show this $k$ satisfies $m^k\equiv k \pmod n$.
The $(*)$ implies $k\equiv l \pmod {\varphi(a)}$ and since $(a,m)=1$, Euler's theorem gives
$$m^{k-l}\equiv m^0=1 \pmod {a}.$$
So we have
$$
a\mid m^{k-l}-1,
b\mid m^l.
$$
But $ab=n$ and so
$$
n\mid m^l(m^{k-l}-1)=m^k-m^l=m^k-k
$$
which is just $m^k \equiv k \pmod {n}$, as required.
$\square$
Note: This appeared as a Problem 4 on USA TST 2007, you might find additional solutions there.
