Avoiding brute force: determining when a specific polynomial in $\mathbb{Q}[x]$ is an integer for any integer $x$

Solution 1:

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$.

Solution 2:

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.

Solution 3:

$$ \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$.

Solution 4:

Fermat's Little Theorem

In particular, this polynomial admits a lot of simplification. $$ \begin{align} 3n^5+5n^3+7n &\equiv2n^3+n&\pmod3\tag{1a}\\ &\equiv2n+n&\pmod3\tag{1b}\\ &\equiv0&\pmod3\tag{1c} \end{align} $$ Explanation:
$\text{(1a)}$: reduce coefficients $\bmod3$
$\text{(1b)}$: apply Fermat's Little Theorem
$\text{(1c)}$: $3n\equiv0\pmod3$

$$ \begin{align} 3n^5+5n^3+7n &\equiv3n^5+2n&\pmod5\tag{2a}\\ &\equiv3n+2n&\pmod5\tag{2b}\\ &\equiv0&\pmod5\tag{2c} \end{align} $$ Explanation:
$\text{(2a)}$: reduce coefficients $\bmod5$
$\text{(2b)}$: apply Fermat's Little Theorem
$\text{(2c)}$: $5n\equiv0\pmod5$

Thus, $3n^5+5n^3+7n\equiv0\pmod{15}$.

Binomial Polynomials

In general, any polynomial that takes only integer values can be written as an integer combination of binomial polynomials: $$ \frac{3n^5+5n^3+7n}{15}=24\binom{n}{5}+48\binom{n}{4}+32\binom{n}{3}+8\binom{n}{2}+\binom{n}{1}\tag3 $$

The Computatation of the Coefficients

For a degree $d$ polynomial $P$, $$ P(n)=\sum_{k=0}^dc_k\binom{n}{k}\tag4 $$ We can compute $c_n$ inductively, using $$ P(n)-\overbrace{\sum_{k=0}^{n-1}c_k\binom{n}{k}}^{\substack{\text{using the $c_k$}\\\text{computed}\\\text{previously}}}=c_n\overset{\substack{1\\[3pt]\downarrow\\[3pt]\,}}{\binom{n}{n}}+\overbrace{\sum_{k=n+1}^dc_k\binom{n}{k}}^{\substack{\text{the binomial}\\\text{coefficients}\\\text{are $0$}}}\tag5 $$

$c_0=P(0):$ $$ c_0=\frac{3\cdot0^5+5\cdot0^3+7\cdot0}{15}=0 $$ $c_1=P(1)-c_0\binom{1}{0}:$ $$ c_1=\frac{3\cdot1^5+5\cdot1^3+7\cdot1}{15}-0\binom{1}{0}=1 $$ $c_2=P(2)-c_0\binom{2}{0}-c_1\binom{2}{1}:$ $$ c_2=\frac{3\cdot2^5+5\cdot2^3+7\cdot2}{15}-0\binom{2}{0}-1\binom{2}{1}=8 $$ $c_3=P(3)-c_0\binom{3}{0}-c_1\binom{3}{1}-c_2\binom{3}{2}:$ $$ c_3=\frac{3\cdot3^5+5\cdot3^3+7\cdot3}{15}-0\binom{3}{0}-1\binom{3}{1}-8\binom{3}{2}=32 $$ $c_4=P(4)-c_0\binom{4}{0}-c_1\binom{4}{1}-c_2\binom{4}{2}-c_3\binom{4}{3}:$ $$ c_4=\frac{3\cdot4^5+5\cdot4^3+7\cdot4}{15}-0\binom{4}{0}-1\binom{4}{1}-8\binom{4}{2}-32\binom{4}{3}=48 $$ $c_5=P(5)-c_0\binom{5}{0}-c_1\binom{5}{1}-c_2\binom{5}{2}-c_3\binom{5}{3}-c_4\binom{5}{4}:$ $$ c_5=\frac{3\cdot5^5+5\cdot5^3+7\cdot5}{15}-0\binom{5}{0}-1\binom{5}{1}-8\binom{5}{2}-32\binom{5}{3}-48\binom{5}{4}=24 $$ Thus, the converted polynomial is $$ \frac{3n^5+5n^3+7n}{15}=0\binom{n}{0}+1\binom{n}{1}+8\binom{n}{2}+32\binom{n}{3}+48\binom{n}{4}+24\binom{n}{5} $$