Consider the $\mathbb{R}$-vector space $\mathbb{R}[X]$ of all polynomials with real coefficients and define an $\mathbb{R}$-linear functional $L: \mathbb{R}[X] \to \mathbb{R}$ by $LX^n = a_n$, $n = 0, 1, 2, \dots$. Thus, if $f = \sum_k \alpha_k X^k$, then $Lf = \sum_k \alpha_k a_k$. Since $(X+1)^n = \sum_{k=0}^n \binom{n}{k} X^k$, $n \ge 1$,
$$L(X+1)^n = \sum_{k=0}^{n} \binom{n}{k} LX^k = \sum_{k=0}^{n} \binom{n}{k} a_k = \sum_{k=0}^{n-1} \binom{n}{k} a_k + a_n = 2a_n = 2LX^n,$$
so $Lf(X+1) = 2Lf(X) - f(0)$ for every polynomial $f$ in $\mathbb{R}[X]$. In particular, take $f = \binom{X}{k}$ and use the relation $\binom{X+1}{k} = \binom{X}{k} + \binom{X}{k-1}$, $k \ge 1$, to get $L\binom{X}{k} = L\binom{X}{k-1}$, $k \ge 1$, and deduce that $L\binom{X}{k} = 1$, $k = 0, 1, 2, \dots$. Further, if a polynomial $f$ in $\mathbb{R}[X]$ is integral valued, i.e., $f(k)$ is integral for every integral $k$, then $f = \sum_k \alpha_k \binom{X}{k}$ for some integers $\alpha_k$, so $Lf = \sum_k \alpha_k$ is an integer. Finally, since $a^{p^m} \equiv a^{p^{m-1}} \pmod{p^m}$ for all integers $a$,
$$f = p^{-m} \left( X^{p^m q+r} - X^{p^{m-1} q+r} \right)$$
is an integral valued polynomial in $\mathbb{R}[X]$, so $Lf = (a_{p^m q+r} - a_{p^{m-1} q+r})/p^m$ is an integer, as required.