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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ try induction ? $\endgroup$– SaikatCommented Feb 26, 2016 at 10:14
-
$\begingroup$ Related : math.stackexchange.com/questions/1630655/… $\endgroup$– lab bhattacharjeeCommented Feb 26, 2016 at 11:34
-
$\begingroup$ For $n=0$ you get $0$, which is divisible by $8640$. Now only $8639$ cases left to check. $\endgroup$– DanielVCommented Feb 26, 2016 at 12:02
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
8
$$ \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} $$
-
1$\begingroup$ That is an interesting technique. Is there a general reason to use ${n \choose k}$ rather than any other polynomial? $\endgroup$– DanielVCommented Feb 26, 2016 at 11:07
-
1$\begingroup$ Could you explain where the first equality comes from? Repeated differences? $\endgroup$– lhfCommented Feb 26, 2016 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 ♦Commented Feb 26, 2016 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 ♦Commented Feb 26, 2016 at 15:37
-
1$\begingroup$ @robjohn Fantastic, thank you for referring me to that explanation. $\endgroup$– DanielVCommented Feb 26, 2016 at 15:44
$\begingroup$
$\endgroup$
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)$.
answered Feb 26, 2016 at 10:20
$\begingroup$
$\endgroup$
2
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.
-
-
$\begingroup$ There is now also an example, for more details look at wythagoras solution. $\endgroup$– user302982Commented Feb 26, 2016 at 10:23
$\begingroup$
$\endgroup$
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$
