# Is this number an integer?

I ran across this problem on a practice Putnam worksheet. Completely stumped.

Is $$\large \frac{m^{6} + 3m^{4} + 12m^{3} + 8m^{2}}{24}$$ an integer for all $m \in \mathbb{N}$?

I suspect it is an integer for any $m$. It checks out for small cases.

Any hints for proving the general case?

• A polynomial takes integer values iff it is a $\Bbb Z$-linear combination of binomial coefficients $m\mapsto\binom{m}{k}$. Mar 24, 2018 at 8:26
• There are two terms with cubic powers in the numerator, is that correct? Mar 24, 2018 at 8:28
• It is enough to show that it is divisible by $3$ for $m=0,1,2$ and divisible by $8$ for $m=0,1,2,3,4,5,6,7$ Mar 24, 2018 at 8:43
• Is this a running math contest ? Mar 24, 2018 at 8:44
• @Peter as I stated, the problem is on a practice Putnam worksheet. The Putnam runs every December. Mar 24, 2018 at 18:10

It is always an integer. A standard "brute force" approach is simply to show that each factor of 24 divides the expression in the numerator. This is equivalent to showing that 3 and 8 both divide it in all cases.

The case of the factor 3 splits into two sub cases: one where m is divisible by 3 and one where it is not. If m is divisible by 3 then clearly the numerator is also divisible by 3 and we are done. If m is not divisible by 3, we use the fact that $m^2\equiv 1 \mod 3$ to get $m^6+3m^4+12m^3+8m^2\equiv 1+8\equiv 9\equiv 0\mod 3$ and we are done.

Now we need to prove that 8 divides the expression. We factor it as $m^2(m^4+3m^2+12m+8)$. Clearly there are two subcases: m is either even or odd. If m is even the two factors in the previous factorized form are even, and further, the first factor is a square meaning divisible by 4, hence the two factors together are divisible by 8 and we are done. If m is odd, we can forget the $m^2$ factor since it is odd. We focus on showing that $m^4+3m^2+12m+8\equiv m^4+3m^2+4m\mod 8$ is in fact $0\mod 8$. Here I simply did case work on $m\equiv \{1,3,5\}\mod 8$ (since m is odd) since it isn't too much casework.

• I like this approach. Mar 24, 2018 at 18:11

With this being contest math I suspect the contestant is supposed to recognize the substituted cycle index of the face permutations of the cube under rotations, which is

$$Z(F) = \frac{1}{24} \left(a_1^6 + 6a_1^2a_4 + 3a_1^2a_2^2 + 8a_3^2 + 6a_2^3\right).$$

Hence the formula counts the number of colorings of the faces of the cube with at most $m$ colors and must therefore be an integer.

This cycle index has appeared at MSE several times, consult e.g. this MSE link.

You can just compute $f(m)$ at $7$ consecutive integers. If these values are all integers, then $f(m)$ is always an integer because of Newton's interpolation formula. Try $m=-3,\dots,3$.

This can also be tackled using Mathematical induction. It is clear that m=1 holds. Assume it holds for a number k.Substitue k+1in place of k and cancel the divisors of 24 and then we get another polynomial.Then we must start the whole process for this polynomial(ie prove that 24 divides the new polynomial).Eventually the statement is proved.

By noting the values at $m=0$, $m=1$, ... $m=6$, it is easy to compute $$\tfrac{m^6+3m^4+12m^3+8m^2}{24} =\textstyle30\binom{m}{6}+75\binom{m}{5}+68\binom{m}{4}+30\binom{m}{3}+8\binom{m}{2}+\binom{m}{1}$$