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(\mathrm{mod}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(\mathrm{mod}{n}_1)$. This leads to $a^k+k=n_{1}q$, and we represent $q=p{q}_1+r$ with $0⩽r<p$. Thus, $a^k+k=n_1(p{q}_1+r)\equiv r{n}_1(\mathrm{mod}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 $$Ac\equiv 1(\mathrm{mod}p)⟺(p-1)rAc\equiv (p-1)r\equiv -r(\mathrm{mod}p).$$ This leads to $$p^{b-1}{q}_1^{a_1}\cdots q_k^{a_k}r(p-1)Ac\equiv -p^{b-1}{q}_1^{a_1}\cdots q_k^{a_k}r(\mathrm{mod}{p}^b{q}_1^{a_1}\cdots q_k^{a_k}).$$ Hence, we have $$q_1\cdots q_k\phi (n)rc\equiv -n_{1}r(\mathrm{mod}n).$$ Finally, define $d=q_1\cdots q_{k}c$ or $c$, if $n$ has one prime divisor. We get $r\phi (n)d\equiv -n_{1}r(\mathrm{mod}n)$. Put $m=r\phi (n)d+k$. Then, $$\begin{array}{rl}{a}^m+m& \equiv a^{r\phi (n)d+k}+r\phi (n)d+k\equiv a^k+k-n_{1}r\\ & \equiv n_{1}r+r\phi (n)d\equiv n_{1}r-n_{1}r\equiv 0(\mathrm{mod}n)\end{array}$$ $\square$