<s>[INST] Avoiding brute force: determining when a specific polynomial in $\mathbb{Q}[x]$ is an integer for any integer $x$ I have to prove that $\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n$ is an integer for any $n$. I solved this by brute-force, exhausting all the possibilities methods. I was wondering if there was a way to solve this at-a-glance with some sort of theory? Because
Although my answer is correct, I was apparently supposed to use some theory to answer this question.
I started by putting everything on common denominator and factoring out $n$:
$$\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n = \frac{n(3n^4+5n^2+7)}{15}$$
then I proceeded to plug in $\pm1 ,\pm2, \pm3 ,..., \pm7$ into $3n^4+5n^2+7 \pmod {3,5,\text{ or }15}$
$$3(\pm 1)^4 +5(\pm 1)^2 +7 \equiv 15 \equiv 0 \pmod{15}$$
$$3(\pm 2)^4 +5(\pm 2)^2 +7 \equiv 75 \equiv 5\cdot 15 \equiv 0 \pmod{15}$$
$$3(\pm 3)^4 +5(\pm 3)^2 +7 \equiv 295 \equiv 0 \pmod{5} \text{ while } n \equiv 0 \pmod 3$$
$$3(\pm 4)^4 +5(\pm 4)^2 +7 \equiv 855 \equiv 57\cdot 15\equiv 0 \pmod{15}$$
$$3(\pm 5)^4 +5(\pm 5)^2 +7 \equiv 2007 \equiv 0 \pmod{3}\text{ while } n \equiv 0 \pmod 5$$
$$3(\pm 6)^4 +5(\pm 6)^2 +7 \equiv 4075 \equiv 0 \pmod{5}\text{ while } n \equiv 0 \pmod 3$$
$$3(\pm 7)^4 +5(\pm 7)^2 +7 \equiv 7455 \equiv 497 \cdot 15\equiv 0 \pmod{15}$$
to conclude that if $n\equiv 0 \pmod {15}$ then $\frac{n}{15}$ is an integer from which $\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n$ is an integer,
and if $n \not\equiv 0 \pmod {15}$ then either $3n^4+5n^2+7 \equiv 0 \pmod{15}$ or $n \equiv 0 \pmod 3$ and $ 3n^4+5n^2+7 \equiv 0 \pmod{5}$ or $n \equiv 0 \pmod 5$ and $ 3n^4+5n^2+7 \equiv 0 \pmod{3}$ from which the statement is clearly true.
Is there a less brute-force-ish way of concluding this? Is there some theory I should be using that would cause me to not be excessively lengthy in calculation if I were given different, larger numbers than $15$?
 [/INST] The question asks how to prove a polynomial
$\,f(n)\,$ takes only integer values for any
integer $\,n\,.$ If the polynomial is of
degree $0$, then it is a constant and if
that constant is an integer we are done.
If the polynomial is of degree $1$, then if
any two consecutive values,
$\,f(k), f(k+1)\,$ are integers,
then it is an arithmetic progression and
we are done. In general, for any degree
$\,d\,$ polynomial $\,f(n),\,$ it is
sufficient to verify that
$$f(k),f(k+1), \dots,f(k+d-1) $$ are all integers for some
integer $\,k,\,$ which implies that the polynomial takes on only integer values for all integer $\,n.\,$
A proof of this can be done by using a
difference table to find an explicit
expression for the polynomial as a sum of
binomial coefficients. For example, using
the particular polynomial in the question,
$$ f(n) := \frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n $$
the forward difference table is:
$$ \begin{matrix}
\Delta^6f(n)  &&&&&&& 0 \\
\Delta^5f(n)  &&&&&& 24 && 24 \\
\Delta^4f(n)  &&&&& 48 && 72 && 96 \\
\Delta^3f(n)    &&&& 32 && 80 && 152 && 248 \\
\Delta^2f(n)    &&& 8 && 40 && 120 && 272 && 520\\
\Delta f(n)   && 1 && 9 && 49 && 169 && 441 && 961  \\
f(n)    & 0 && 1 && 10 && 59 && 228 && 669 && 1630 \\
n      & 0 && 1 && 2 && 3 && 4 && 5 && 6
\end{matrix} $$
where the 5th differences are constant as expected for a
5th degree polynomial. Thus,
$$ f(n) = 0{n \choose 0} +1{n \choose 1} + 8{n \choose 2} 
 + 32{n \choose 3}  + 48{n \choose 4}  + 24{n \choose 5}$$
where the coefficient of $\,{n\choose k}=\Delta^kf(0),\,$
the $k$th difference of $\,f\,$ at zero.
The Wikipedia article finite difference
explains some of this  theory. The forward differences of $\,f\,$ are
$$ \Delta f(n) := f(n+1)-f(n),
\:\: \Delta^2 f(n) := \Delta f(n+1) - \Delta f(n), \:\: \dots. $$
In this particular case, the 1st backward difference is the
OEIS sequence A058031
$$ a_n := (n^2-n+1)^2 = \nabla f(n) := f(n)-f(n-1).$$
Thus the polynomial is the partial sums of an integer sequence
and therefore is an integer sequence itself.
</s>