First, for any $m < n$, let $k = n - m$, and take a positive integer $t$ such that $tk > n$. Consider that $tk$ divides $a_n + a_{tk-n}$ and $(t-1)k$ divides $a_m + a_{tk-n}$, from which we obtain that $a_n$ and $a_m$ have the same remainder upon division by $k$, that is, $n - m$ divides $a_n - a_m$.
By Lagrange interpolation, there exists a polynomial $f(x)$ with rational coefficients of degree at most 100 such that for $k = 1, 2, \dots, 101$, we have $f(k) = a_k$. We now prove that $f(n) = a_n$.
Let $N$ be a positive integer such that $Nf(x)$ is a polynomial with integer coefficients. Consider the function $h$ defined on the set of integers by $h(n) = N(f(n) - a_n)$; then $h$ takes the value $0$ at $1$ through $101$, and, by what was stated in the first paragraph together with the fact that $Nf(x)$ is a polynomial with integer coefficients, $h$ satisfies $(n-m)|(h(n)-h(m))$. Moreover, since $f(x)$ is a polynomial of degree at most 100, from $a_n \le n^{100}$ we know there exists a constant $M > 0$ such that $|h(n)| \le M(n^{100} + 1)$.
For any positive integer $n$, compare $h(n)$ and $h(k)$, where $k = 1, \dots, 101$. Since $h(k) = 0$, from $(n-k)|(h(n)-h(k))$ we get that $h(n)$ must be a multiple of $(n-101), \dots, (n-1)$; the pairwise common factors of these numbers are at most 100, so their least common multiple is $\ge (n-101)^{101}/(100^{5050})$, and $h(n)$ must be a multiple of their least common multiple. When $n$ is sufficiently large, we have $(n-101)^{101}/(100^{5050}) > M(n^{100}+1)$, and at this point we conclude $h(n) = 0$.
For any integer $m$, for any sufficiently large $n$ we have $(n-m)|h(m)$, and hence $h(m) = 0$, which completes the proof!