Let $\ell$ be the length of the cycle of the sequence $a, a^2, a^3, \dots$ mod $c$. Thus
$$a^{\ell + \ell k} \equiv a^\ell \pmod{c} \quad (*)$$
for all positive integer $k$ and $\ell$ large enough.

Let $d = \gcd(\ell, c)$. The multiples of $\ell$ mod $c$ are the multiples of $d$. Let's prove that if $c > 1$ then $d < c$. Since $d$ divides $c$, $d \leq c$.
Suppose that $d = c$. So $c$ divides $\ell$. Note that it's not possible that two equal remainders appear in the same cycle, because $a' \equiv a' \pmod{c}$ implies $a'^c \equiv a'^c \pmod{c}$, that is, $i-j$ is multiple of $\ell$, contradiction. Hence the length of the cycle of $a, a^2, a^3, \dots$ mod $c$ does not exceed $c$. Thus, if $c$ divides $\ell$, $c = \ell$. This means that $c$ divides some $a^n$ and also every bigger power of $a$. Hence, $\ell = 1$ and $c = 1$.
The problem now goes by induction on $c$. It is obvious for $c = 1$. Suppose that $c > 1$ and that the result is true for every positive integer less than $c$. Then it is true for $d$, because $d < c$. By the induction hypothesis, there are sufficiently large $n_0, n_1, n_2, \dots, n_{d-1}$ such that
$$a^{n_i} + n_i \equiv i \pmod{d}$$
for every $i = 0, 1, 2, \dots, d-1$.
Let $b = qd + r$, with $0 \leq r < d$. So, from $a^{n_r} + n_r = r + md$ and $(*)$,
$$a^{n_r + \ell k} + (n_r + \ell k) \equiv a^{n_r} + (n_r + \ell k) \equiv r + md + \ell k \pmod{c} \quad (**)$$
But, when $k$ varies, $\ell k \pmod{c}$ goes through all multiples of $d$. Thus there exists $k$ such that $\ell k \equiv (q-m)d \pmod{c}$. Plugging it in $(**)$,
$$a^{n_r + \ell k} + (n_r + \ell k) \equiv r + md + (q - m)d \pmod{c} \\ \iff a^{n_r + \ell k} + (n_r + \ell k) \equiv r + qd \equiv b \pmod{c}$$
Hence, we can take $x = n_r + \ell k$ and the induction step is complete.