7
$\begingroup$

I found this problem in a book, I can't solve it unfortunately. Prove that for all integer values $n$, $n^9 - 6n^7 + 9n^5 - 4n^3$ is divisible by $8640.$ So far I've noticed that $8460 = 6! \times 12$, also I've tried to simplify that expression and I've found that it's equal to this $n^3(n^3-3n-2)(n^3-3n+2)$, but I can't move on after that.

$\endgroup$
6
$\begingroup$

We can further note that $-1$ is a root of $n^3-3n-2$, and that $1$ is a root of $n^3-3n+2$.


You can find these roots by the Rational Root theorem:

Rational root theorem. All rational roots have the form $\frac{p}{q}$,with $p$ a divisior of the constant term and $q$ a divisior of the first coefficient.

Other techniques can also be found in this question and its answers.


Then we simplify it to \begin{align*} n^3(n+1)(n^2-n-2)(n-1)(n^2+n-2) &= n^3(n+1)(n-2)(n+1)(n-1)(n+2)(n-1)\\ &=n^3(n+1)^2(n-1)^2(n-2)(n+2) \end{align*}


There are 6 factors two in 8640.

  • If $n$ is even, $n, n-2$ and $n+2$ are even, and furthermore at least one of them is divisible by $4$, which gives 6 factors 2.
  • If $n$ is odd, $n-1$ and $n+1$ are even, and furthermore at least one of them is divisible by $4$, which gives 6 factors 2.

There are 3 factors three in 8640.

  • If $n \equiv 0 \mod 3$, then $n$ is divisible by 3, and then $27 \mid n^3$.
  • If $n \equiv 1 \mod 3$, then $n-1$ and $n+2$ are divisible by 3.
  • If $n \equiv 2 \mod 3$, then $n+1$ and $n-2$ are divisible by 3.

The factor 5 can be taken care of since the product is a multiple of five consecutive integers, namely a product of $(n-2)(n-1)n(n+1)(n+2)$.

$\endgroup$
7
$\begingroup$

$$ \begin{align} &n^9-6n^7+9n^5-4n^3\\ &\small=362880\binom{n}{9}+1451520\binom{n}{8}+2298240\binom{n}{7}+1814400\binom{n}{6}\\ &\small+734400\binom{n}{5}+138240\binom{n}{4}+8640\binom{n}{3}\\ &=\small8640\left[42\binom{n}{9}+168\binom{n}{8}+266\binom{n}{7}+210\binom{n}{6}+85\binom{n}{5}+16\binom{n}{4}+\binom{n}{3}\right] \end{align} $$

$\endgroup$
  • 1
    $\begingroup$ That is an interesting technique. Is there a general reason to use ${n \choose k}$ rather than any other polynomial? $\endgroup$ – DanielV Feb 26 '16 at 11:07
  • 1
    $\begingroup$ Could you explain where the first equality comes from? Repeated differences? $\endgroup$ – lhf Feb 26 '16 at 11:23
  • 1
    $\begingroup$ @Kareem: every polynomial that sends $\mathbb{Z}$ to $\mathbb{Z}$ can be written as an integral combination of binomial coefficients. It is very easy to compute a degree $n$ polynomial by evaluating at $0,1,2,\dots n$. Thus, $\frac{n^9-6n^7+9n^5-4n^3}{8640}$ must be in this form. $\endgroup$ – robjohn Feb 26 '16 at 14:30
  • 1
    $\begingroup$ @lhf: we can compute $a_0$, the coefficient of $\binom{n}{0}$, by $$a_0=P(0)$$ then $$a_1=P(1)-a_0\binom{1}{0}$$ and $$a_2=P(2)-a_0\binom{2}{0}-a_1\binom{2}{1}$$ and $$a_3=P(3)-a_0\binom{3}{0}-a_1\binom{3}{1}-a_2\binom{3}{2}$$ etc. $\endgroup$ – robjohn Feb 26 '16 at 15:37
  • 1
    $\begingroup$ @robjohn Fantastic, thank you for referring me to that explanation. $\endgroup$ – DanielV Feb 26 '16 at 15:44
4
$\begingroup$

If you do complete factorisation you get $$n^9−6n^7+9n^5−4n^3=n^3(n-2)(n-1)^2(n+1)^2(n+2)$$ and $$8640=2^6\cdot 3^3\cdot 5$$ Now just look at different cases. For $2\mid n$ we have $2^3\mid n^3$, $2\mid n-2$, $2\mid n+2$ and either $n-2$ or $n+2$ has the factor $2^2$, so we get $2^6\mid n^9−6n^7+9n^5−4n^3$. Do it for the case $n$ odd and for the other factors in a similar style.

$\endgroup$
  • $\begingroup$ how does this help? $\endgroup$ – Bhaskara-III Feb 26 '16 at 10:21
  • $\begingroup$ There is now also an example, for more details look at wythagoras solution. $\endgroup$ – user302982 Feb 26 '16 at 10:23
3
$\begingroup$

Hints:

  • Note for example $n^3-3n+2 = (n-1)(n^2-n-2) = (n-1)(n+1)(n-2)$. You can factorise completely to a product of terms like $(n-1)$ and $(n+2)$. Do that
  • How many powers of $5$ must the product have?
  • How many powers of $3$? How many powers of $2$? Note for example that one of two consecutive even numbers is a multiple of $4$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.