Let $n,p\geq 1$ be integers, and assume that $p$ is a prime.


**Question.** Does there always exist an integer $m\geq 1$ such that
$p^m\equiv m\pmod{n}$?



On the solvability of the congruence $p^m\equiv m\pmod{n}$
The answer is affirmative when $(p,n)$=1, even without the assumption that $p$ is a prime.


Let us fix $p$ and proceed by induction on $n$. We can assume, without loss of generality, that $p\geq 2$. For $n=1$ the statement is clear. So let us assume that $n\geq 2$, and the statement holds for all proper divisors of $n$. Let $\ell$ be the largest prime factor of $n$, and let $k\geq 1$ be such that $p^k\equiv k\pmod{n/\ell}$. That is, $p^k=k+rn/\ell$ for some $r\geq 1$. We claim that there is $s\geq 1$ such that $m:=k+rs\varphi(n)$ satisfies $p^{m}\equiv {m}\pmod{n}$. Indeed,
$$p^m\equiv p^k=k+rn/\ell\pmod{n},$$
hence it suffices that
$n/\ell\equiv s\varphi(n)\pmod{n}$, i.e.,
$$\frac{n/\ell}{\gcd(n/\ell,\varphi(n))}\equiv s\frac{\varphi(n)}{\gcd(n/\ell,\varphi(n))}\pmod{\frac{n}{\gcd(n/\ell,\varphi(n))}}.$$
The solutions of this congruence are
$$s=t\frac{n/\ell}{\gcd(n/\ell,\varphi(n))},\quad\text{where}\quad 1\equiv t\frac{\varphi(n)}{\gcd(n/\ell,\varphi(n))}\pmod{\ell}.$$
It is straightforward to check that
$$\frac{\varphi(n)}{\gcd(n/\ell,\varphi(n))}\ \mid\ \prod\_{p\mid n}(p-1),$$
hence the left hand side is not divisible by $\ell$. As a result, the last congruence has a unique solution $t\bmod\ell$, and the proof is complete.


