Brazil

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 }(\mathrm{mod}c)(\ast )$$ 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\le 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^{\prime }\equiv a^{\prime }(\mathrm{mod}c)$ implies $a^{\prime c}\equiv a^{\prime c}(\mathrm{mod}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(\mathrm{mod}d)$$ for every $i=0,1,2,\dots ,d-1$. Let $b=qd+r$, with $0\le r<d$. So, from $a^{n_r}+n_r=r+md$ and $(\ast )$, $$a^{n_r+\ell k}+(n_r+\ell k)\equiv a^{n_r}+(n_r+\ell k)\equiv r+md+\ell k(\mathrm{mod}c)(\ast \ast )$$ But, when $k$ varies, $\ell k(\mathrm{mod}c)$ goes through all multiples of $d$. Thus there exists $k$ such that $\ell k\equiv (q-m)d(\mathrm{mod}c)$. Plugging it in $(\ast \ast )$, $$\begin{gathered} a^{n_r+\ell k}+(n_r+\ell k)\equiv r+md+(q-m)d(\mathrm{mod}c) \\ ⟺a^{n_r+\ell k}+(n_r+\ell k)\equiv r+qd\equiv b(\mathrm{mod}c) \end{gathered}$$ Hence, we can take $x=n_r+\ell k$ and the induction step is complete.