, 2015

We prove by induction on $n$. For $n=1$, there is nothing to prove. Suppose $n \ge 2$ and let $d := \gcd(\phi(n), n)$.

Clearly $a$ and $n$ are relatively prime, thus we have $a^d \equiv 1 \pmod{n}$ by Euler's theorem. Since $d \le \phi(n) < n$ and $a^d \equiv 1 \pmod{d}$, there exists $m$ such that $a^m + m \equiv 0 \pmod{d}$ by the induction hypothesis. Hence, there exists a positive integer $r \le n/d$ such that $a^m + m = dr \pmod{n}$. If we choose $s := m + n - dr$ then
$$a^s + s \equiv a^m + m - dr \equiv 0 \pmod{n}$$
and the proof is complete.