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

Question

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.

Answer 1

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.

Answer 2

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.