, 2010

Imagine dividing $P(x)$ by $Q(x)$. We find that
$$\frac{P(x)}{Q(x)} = A(x) + \frac{R(x)}{Q(x)},$$
where $A(x)$ and $R(x)$ are polynomials with rational coefficients, and $R(x)$ is either identically $0$ or has degree less than the degree of $Q(x)$.
By bringing the coefficients of $A(x)$ to their least common multiple, we can find a polynomial $B(x)$ with integer coefficients, and a positive integer $b$, such that $A(x) = B(x)/b$. Suppose first that $R(x)$ is not identically $0$. Note that for any integer $k$, either $A(k) = 0$, or $|A(k)| \ge 1/b$. But whenever $|k|$ is large enough, $0 < |R(k)/Q(k)| < 1/b$, and therefore if $n$ is large enough, $P(a_n)/Q(a_n)$ cannot be an integer.
So $R(x)$ is identically $0$, and $P(x)/Q(x) = B(x)/b$ (at least whenever $Q(x) \neq 0$.)
Now let $n$ be an integer. Then there are infinitely many integers $k$ such that $n \equiv a_k \pmod b$. But $B(a_k)/b$ is an integer, or equivalently $b$ divides $B(a_k)$. It follows that $b$ divides $B(n)$, and therefore $P(n)/Q(n)$ is an integer. $\square$