Saudi Arabian Mathematical Competitions

We generalize the problem to the following problem:
Let $a$ be a given positive integer. For every natural $n$, there is a positive integer $m$ such that $n$ divides $a^{m} + m$.

In fact, we proceed by induction on $n$. Obviously this statement holds for $n = 1$. Now assume $n > 1$ and this statement holds for every natural number less than $n$. Consider two cases:

Case 1: $n = p$ is a prime. If $p \mid a$ we are done. If not, take $m = (a+1)(p-1) + 1$. Then
$$a^{m} + m = a^{(a+1)(p-1)+1} + (a+1)(p-1) + 1 \equiv (a+1)p \equiv 0 \pmod{p}.$$

Case 2: $n$ is a composite. Let $p$ be the largest prime divisor of $n$. Write $n = p^{b} q_{1}^{a_{1}} \cdots q_{k}^{a_{k}}$ as the prime factorization of $n$ and put $n = p n_{1}$.

By induction hypothesis (to $n_{1} < n$), there is a positive integer $k$ such that $a^{k} + k \equiv 0 \pmod{n_{1}}$. This leads to $a^{k} + k = n_{1} q$, and we represent $q = p q_{1} + r$ with $0 \leqslant r < p$. Thus, $a^{k} + k = n_{1}(p q_{1} + r) \equiv r n_{1} \pmod{n}$. Now, put $A = (q_{1} - 1) \cdots (q_{k} - 1)$, or $1$ if $n$ has only one prime divisor.

Since $p$ is the largest prime divisor of $n$, it follows that $A$ and $p$ are coprime. Hence, there is a positive integer $c$ such that
$$A c \equiv 1 \pmod{p} \Longleftrightarrow (p-1) r A c \equiv (p-1) r \equiv -r \pmod{p}.$$
This leads to
$$p^{b-1} q_{1}^{a_{1}} \cdots q_{k}^{a_{k}} r (p-1) A c \equiv -p^{b-1} q_{1}^{a_{1}} \cdots q_{k}^{a_{k}} r \pmod{p^{b} q_{1}^{a_{1}} \cdots q_{k}^{a_{k}}}.$$
Hence, we have
$$q_{1} \cdots q_{k} \varphi(n) r c \equiv -n_{1} r \pmod{n}.$$
Finally, define $d = q_{1} \cdots q_{k} c$ or $c$, if $n$ has one prime divisor. We get $r \varphi(n) d \equiv -n_{1} r \pmod{n}$. Put $m = r \varphi(n) d + k$. Then,
$$\begin{aligned} a^{m} + m &\equiv a^{r \varphi(n) d + k} + r \varphi(n) d + k \equiv a^{k} + k - n_{1} r \\ &\equiv n_{1} r + r \varphi(n) d \equiv n_{1} r - n_{1} r \equiv 0 \pmod{n} \end{aligned}$$
$\square$