# Prove that $6$ divides $n(n + 1)(n + 2)$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows:

Let $$n$$ be an integer such that $$n ≥ 1$$. Prove that $$6$$ divides $$n(n + 1)(n + 2)$$.

Note: An integer $$a$$ divides an integer $$b$$, written $$a|b$$, if there exists $$q ∈ Z$$ such that $$b = qa$$. Alternatively, $$a|b$$ if dividing $$b$$ by $$a$$, $$b ÷ a$$, results in an integer.

Should I do a proof by induction?

All help/input is appreciated!

The links provided by lab bhattacharjee solve the problem in more generality, but for the sake of completeness...

Let us do an inductive proof. For $$n = 0$$ things are trivial. Suppose we know the claim for $$n$$, and we want to prove it for $$n+1$$. By inductive assumption, $$n(n+1)(n+2) = n^3+2n^2 + 2n = 6 q$$ for some $$q$$. Now, $$(n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2) = 6q + 3(n+1)(n+2)$$ A simple argument (use induction again, if you like) shows that $$(n+1)(n+2)$$ is divisible by $$2$$, so you can write $$(n+1)(n+2) = 2p$$. Consequently, $$(n+1)(n+2)(n+3) = 6(q+p)$$ which finishes the problem.

• I think this answer could use an explanation of why induction is not a good approach to this problem. – dfeuer Oct 15 '13 at 20:27
• I think any approach is good, as long as it works. Personally, I believe it is worth it to try and squeeze as much as possible of methods one is familiar with. If the person posing a problem thinks of induction - why not try it? It generalises quite nicely: Suppose you are trying to prove that $f(n)$ is divisible by $M$ for all $n$. Then just check if $M$ divides $f(0)$, and that $g(n) := f(n+1)-f(n)$ is divisible by $M$ for all $n$. For $g(n)$, if things are not already obvious, just apply the same reasoning. For instance, this proves little Fermat. – Jakub Konieczny Oct 16 '13 at 9:53
• isn't it n(n + 1)(n+2) instead of (n + 2)(n + 3)n ? – RiaD Dec 18 '15 at 9:00

$n$ is either even or odd. Also, it must be congruent, modulo $3$, to either $0$, $1$, or $2$.

Another possibility:

$$\frac{n(n+1)(n+2)}{6}$$ equals the binomial coefficient $$\binom{n+2}{3}$$ which is an integer (since it is the number of 3-element subsets of an ($$n+2$$)-element set).

• It's the same as asking why ${ n+2 \choose 3}$ is an integer. – user5402 Dec 4 '15 at 17:52

The product $n(n+1)(n+2) \equiv 0\ (\mathrm{mod}\ 2)$, since if $n$ is even the product will be even, and if $n$ is odd then $n+1$ will be even and again the product is even.

We also know that $n(n+1)(n+2) \equiv 0\ (\mathrm{mod}\ 3)$. You can prove this by notating that $n\ \mathrm{mod}\ 3$ must be $0, 1,$ or $2$, and all of these cases imply the product is divisible by $3$. $$n\equiv0\ (\mathrm{mod}\ 3)\implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3),$$ $$n \equiv1\ (\mathrm{mod}\ 3)\implies n+2\equiv 0\ (\mathrm{mod}\ 3)\implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3),$$ $$n\equiv2\ (\mathrm{mod}\ 3)\implies n+1 \equiv 0\ (\mathrm{mod}\ 3) \implies n(n+1)(n+2)\equiv0\ (\mathrm{mod}\ 3).$$

Therefore $n(n+1)(n+2)$ is divisible by $2$ and by $3$, which implies it is divisible by $6$.

Either one of $n$, $n+1$ and $n+2$ is divisible by $3$, because $n$ is either in the form of $3k$, $3k+1$ or $3k+2$. We also have either one of $n$ or $n+1$ is divisible by $2$ because they are two consecutive natural numbers. Thus, the product of $n$, $n+1$ and $n+2$ is always divisible by $2*3=6$.

If we let $m=n+1$, we need to prove that $6 \vert m(m^2-1)$ for all $m \geq 2$. Equivalently, we want to show that $$m^3 \equiv m \bmod6$$ First note that $m \equiv 0,1,2,3,4,5 \pmod 6$. Now observe that following: $$m \equiv 0 \bmod 6 \implies m^3 \equiv 0^3 \bmod 6 \implies m^3 \equiv 0 \bmod6$$ $$m \equiv 1 \bmod 6 \implies m^3 \equiv 1^3 \bmod 6 \implies m^3 \equiv 1 \bmod6$$ $$m \equiv 2 \bmod 6 \implies m^3 \equiv 2^3 \bmod 6 \implies m^3 \equiv 8 \bmod6 \implies m^3 \equiv 2 \bmod6$$ $$m \equiv 3 \bmod 6 \implies m^3 \equiv 3^3 \bmod 6 \implies m^3 \equiv 27 \bmod6 \implies m^3 \equiv 3 \bmod6$$ $$m \equiv 4 \bmod 6 \implies m^3 \equiv 4^3 \bmod 6 \implies m^3 \equiv 64 \bmod6 \implies m^3 \equiv 4 \bmod6$$ $$m \equiv 5 \bmod 6 \implies m^3 \equiv 5^3 \bmod 6 \implies m^3 \equiv 125 \bmod6 \implies m^3 \equiv 5 \bmod6$$ Hence, in all cases, we have $m^3 \equiv m \bmod 6$, which means that $$6 \vert (m^3-m) \implies 6 \vert n(n+1)(n+2)$$

If a number is divisible by $6=2\cdot 3$, then it must be divisible by $2$, and also by $3$.

Look at $$n(n+1)(n+2)$$ if $n$ is not divisible by $2$, will any of the other factors be? If $n$ is not divisible by $3$ will any of the factors be?