# Prove that $6$ divides $n^3+11n$?

How can i show that $$6\mid (n^3+11n)$$

My thoughts: I show that $$2\mid (n^3+11n)$$ $$3\mid (n^3+11n)$$

And $$n^3+11n=n\cdot (n^2+11)$$ And if $n=x\cdot 3$ for all $x \in \mathbb{N}$ then: $$3\mid (n^3+11n)$$ And if not:

The cross sum of$$n^2+11$$ is multiple of 3.

Can this be right or is there a simple trick?

$$n^3+11n=\underbrace{(n-1)n(n+1)}_{\text{Product of three consecutive integers}}+12n$$

It is easier to understand the part for factor $3$ to check if $n^3+11n = 0 \pmod 3$.

Then either $n = 0 \pmod 3$ or $n = \pm 1 \pmod 3$.

The $n^2 + 11$ is then $0 \pmod 3$.

• Nice approach +1 – Shailesh Feb 26 '16 at 11:38

You can also prove this by induction.

$$(n+1)^3+11(n+1)=(n^3+11n) + 3n(n+1)$$

$6$ divides the first part by induction hypothesis. Then $3$ divides $3$ and $2$ divides $n(n+1)$ (either $n$ or $n+1$ is even) so $6$ divides $3n(n+1)$.

$$n^3+11n = 12 \binom{n}{1} + 6 \binom{n}{2} + 6 \binom{n}{3} = 6\left(2 \binom{n}{1} + \binom{n}{2} + \binom{n}{3}\right)$$

This is obtained by using repeated differences and Newton's interpolation formula: $$\begin{array}{llll} 0 & 12 & 30 & 60 & 108 & \\ 12 & 18 & 30 & 48 & \\ 6 & 12 & 18 & \\ 6 & 6 & \\ 0 & \\ \end{array}$$

• This technique seems to be a @robjohn favorite. – lhf Feb 26 '16 at 11:43

$$(n+1)(n+2)(n+3) = n^3 + 6n^2 + 11n + 6.$$

• (Essentially the same as lab bhattacharjee's answer.) – Unit Feb 26 '16 at 14:04
• It may be essentially the same, but +1 -- because it comes more naturally looking at the given expression. – Shailesh Feb 26 '16 at 15:52

By brute force:

$$(n^3+11n)\bmod6\equiv(n\bmod6)^3+11(n\bmod6)\mod6$$ and you can proceed by trying the integers $0$ to $5$.

Mentally, $$0,12,30,60,108,180.$$

You can speed-up the computation by dropping any multiple of $6$ you meet and by using $-n$ instead of $+11n$.

Incrementally:

Compute the delta between two consecutive terms

$$(n+1)^3+11(n+1)-n^3-11n=3n(n+1)+12.$$

As one of $n$ and $n+1$ is certainly even, the delta is divisible by $6$.

The property holds for all $n$, as $0^3+11\cdot0$ is divisible by $6$.

Here is a proof by induction,

1. setting $n=1$, one should get $$n^3+11n=1^3+11\cdot 1=12$$ obviously, the above number $12$ is divisible by $6$ hence statement is true for $n=1$.

2. Assume that the number $n^3+11n$ is divisible by $6$ for $n=k$ then $$k^3+11k=6\lambda$$or $$k^3=6\lambda-11k\tag 1$$

3. Now, setting $n=k+1$, $$(k+1)^3+11(k+1)$$$$=k^3+3k^2+14k+12$$ $$=6\lambda-11k+3k^2+14k+12$$ $$=6\lambda+3(k^2+k+4)$$ since, $k^2+k+4$ is even for all integer $k$ hence setting $k^2+k+4=2m$, $$=6\lambda+3(2m)$$ $$=6(\lambda+m)$$ since, $(\lambda +m)$ is an integer hence, the above number $6(\lambda+m)$ is divisible by $6$

Hence, $n^3+11n$ is divisible by $6$ for all integers $n\ge 1$

• OP was asking for a simple trick. – Shailesh Feb 26 '16 at 11:36

using mathematical induction

crucial step is $$p(n)\Rightarrow p(n+1)$$

Let $$p(n)=n^3+11n=6k$$ then $$p(n+1)=(n+1)^3+11(n+1)=n^3+3n^2+3n+1+11n+11=$$ $$=6k+3n^2+3n+12=6k+6(\frac{n^2+n}{2}+2)=6(k+\frac{n(n+1)}{2}+2)$$

• I ask downvoter what is wrong with my answer! – Adi Dani Jul 30 '16 at 7:40