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$?
 A: 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.
A: To show that $15$ divides $n(3n^4+5n^2+7)$, show that $3$ and $5$ do.
$3$ does because either $3$ divides $n$ or $n^2\equiv1\pmod3$ by Fermat's little theorem,
in which case $3n^4+5n^2+7\equiv5n^2+7\equiv5+7=12\equiv0\pmod3.$
$5$ does because either $5$ divides $n$ or $n^4\equiv1\pmod5$ by Fermat's little theorem,
in which case $3n^4+5n^2+7\equiv3n^4+7\equiv3+7=10\equiv0\pmod5$.
A: $$ \begin{align}f(n+1)-f(n)&=\frac{(n+1)^5-n^5}5+\frac{(n+1)^3-n^3}3+\frac7{15}
\\&=\frac{5n^4+10n^3+10n^2+5n+1}5+\frac{3n^2+3n+1}3+\frac7{15}\\&=\text{integer}+\frac15+\frac13+\frac 7{15}\end{align}$$
is an integer for all integers $n$ and so is $f(0)$. The claim follows by induction.

Here's a generalization for you: Suppose $p_1,p_2,\ldots,p_m$  are primes, $a_1,a_2,\ldots,a_m$ are integers and $c$ is real. Let
$$ f(n)=\frac{a_1n^{p_1}}{p_1}+\frac{a_2n^{p_2}}{p_2}+\cdots +\frac{a_mn^{p_m}}{p_m}+cn.$$
If $f(1)$ is an integer, then $f(n)$ is an integer for all integers $n$.
A: You can cut some work by just looking at the remainder mod $3$.
Let $n=3q+r$. Easy calculation gives
$$\frac15(3q+r)^5+\frac13(3q+r)^3+\frac{7}{15}(3q+r) = \text{some integer} + \frac{243q^5+7q}{5} + \frac{r^5}5+\frac{r^3}3+\frac{7r}{15}.$$
By Little Fermat we have $q^5 \equiv q \pmod{5}$ so
$$243q^5+7q \equiv 250q \equiv 0\pmod{5}.$$
The second term
$$\frac{r^5}5+\frac{r^3}3+\frac{7r}{15}$$
is the same as the original expression but you only have to check $r=0,1,2$ which is almost trivial.
