# Positive Integer Divison Proof [closed]

Prove that $6|n(n + 1)(n + 2)$ for any integer $n ≥ 1$

I have attempted to do this but never seem to prove it.

As $3$ positive consecutive integers, either $n$, $n+1$, or $n+2$ must be divisible by $3$.

As $2$ positive consecutive integers, either $n$ or $n+1$ must be divisible by $2$.

Therefore, since $n(n + 1)(n + 2)$ is divisible by $2$ and $3$ ($2$ and $3$ are relatively prime numbers), it must be divisible by $6$.

• Alternatively, instead of tightening the requirements (+relatively prime), we could weaken the conclusion: "it must be divisible by their l.c.m., 6." – DSM Feb 8 '18 at 12:45

Alt. hint: $\;\displaystyle\,\dfrac{n(n+1)(n+2)}{6} = \binom{n+2}{3}\;$ is an integer for all $\,n \ge 1\,$.

• the standard argument that this ratio is really an integer is the same that Yash Jain proposes. – WorldSEnder Feb 8 '18 at 3:09
• @WorldSEnder Alt. hint The "alt." in my answer stands for "alternative". – dxiv Feb 8 '18 at 3:26
• Ah yes, I realize now that the unique contribution is introducing combinatorics which I mistakenly thought to be a tag in the question. – WorldSEnder Feb 8 '18 at 4:26
• Wish the downvoter had left a comment why. – dxiv Feb 8 '18 at 17:13

If you divide a number by $3$, you will get a remainder of either $0$, $1$ or $2$.

If $\frac{n}{3}$ has a remainder of $0$, $n$ is divisible by $3$ and you're done (with proving divisibility by $3$).

If not, $\frac{n}{3}$ has a remainder of either $1$ or $2$. If it has a remainder of $1$, you can rewrite $n$ as $3k + 1$, which means you can rewrite $n+2$ as $3k+3 = 3(k+1)$, which is clearly divisible by $3$.

If $\frac{n}{3}$ has a remainder of $2$, then $n$ can be written as $3k+2$ and therefore $n+1$ as $3k+3$, which is again clearly divisible by $3$.

Going over the same process for $2$ shows that your number also has to be divisible by $2$, and if a number is divisible by both $2$ and $3$, it's divisible by $2 \cdot 3 = 6$. This is only true because $2$ and $3$ are co-prime. As an example of why this isn't true for every case, consider a number divisible by $2$ and $4$; it isn't necessarily divisible by $8$.

Using the same logic about remainders, in general any number $n (n+1)...(n+m)$ for $n \geq 1$ is going to be divisible by all integers from $1$ to $m+1$.

A more generalized result, by induction:

Define $p_r(n):=n(n+1)(n+2)\cdots (n+r-1)=\prod_{i=n}^{n+r-1} i$

Assertion to prove: $r!$ divides $p_r(n)$ for all $r,n \in \Bbb N$

Base cases:
$p_r(1) = r!$ is divisible by $r!$
$p_1(n) = n$ is divisible by $1$

Hypothesis: assume $p_t(k-1)$ is divisible by $t!$ and $p_{t-1}(k)$ is divisible by $(t-1)!$

Now
\begin{align}p_t(k) &= k(k+1)(k+2)\cdots (k+t-1) \\ &= (k-1)k(k+1)\cdots(k+t-2) + t\cdot k(k+1)\cdots(k+t-2) \\ &= p_t(k-1) + t\cdot p_{t-1}(k) \end{align}

So by the hypothesis both parts are divisible by $t!$, proving the assertion.

Specific case: $p_3(n)$ is divisible by $3!=6$

In $\Bbb F_2$: $$n(n + 1)(n + 2) = n^2(n + 1) = n^3 + n^2 = n + n = 0.$$

In $\Bbb F_3$: $$n(n + 1)(n + 2) = n^3 + (1 + 1 + 1)n^2 + (1 + 1)n = n + 0 + (1 + 1)n = 0.$$

Assumption: There are $n$ where $6$ doesn't divide $n(n+1)(n+2)$.

Let $x$ be the smallest $n$ where $6$ doesn't divide $n(n+1)(n+2)$.

Since $6|1\times 2\times 3$ and $6|2\times 3\times 4$ that $x$ has to be at least $3$.

If $6$ doesn't divide $x(x+1)(x+2)$ then it doesn't divide $x(x+1)(x+2)-6x^2 = ... = (x-2)(x-1)x = (x-2)(x-2+1)(x-2+2)$.

So the statement isn't true for $x-2$ and that is a contradiction to the fact that $x$ is smallest $n$ where the statement isn't true.

• Isn't this kinda wrong tho? You cannot take the smallest number with that assumtion since there may be an infinite unbounded set of x such that x(x+1)(x+2) doesnt divide 6. – h8red Feb 8 '18 at 15:16
• @h8red Yes, the assumption should be: "There are positive integer $n$ where ..." Then the set has a lower bound of 1. – Etoplay Feb 13 '18 at 12:56

If $n$ is even: $n = 2k \implies n(n+1)(n+2) = 2k(2k+1)(2k+2) = 2k(4k^2+6k+2)= 8k^3+12k^2+4k = 6k^3+12k^2 + 6k+2k^3-2k$. Observe that if $3 \nmid k\implies k^2-k = 0\pmod 3$ by Fermat Little's theorem. Thus $2k^3 - 2k = 0\pmod 6$. Thus $6 \mid n(n+1)(n+2)$. If $n$ is odd, then $n = 2k+1\implies n(n+1)(n+2) = (2k+1)(2k+2)(2k+3)= (m-1)m(m+1)$ with $2 \mid m = 2k+2$. So if $3 \nmid m\implies m^2-m = 0\pmod 3$ again by Fermat Little's theorem. Thus $6 \mid n(n+1)(n+2), \forall n \ge 1$.

• did you try to solve it in a difficult way? – mesel Feb 8 '18 at 2:54

Easier Induction:

• Base case: $n = 1$ $\implies n(n+1)(n+2) = 6$ and $6|6$
• Hypothesis: There exists $n$ such that $6|n(n+1)(n+2)$

• Thesis: (if it is true for $n$, it is true for $n+1$)

$(n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+3)$ and

$6|n(n+1)(n+2)$ for hypothesis, $6|3(n+1)(n+2)$ because $(n+1)(n+2)$ is necessarily even.

so $(n+1)(n+2)(n+3)$ is equal to the sum of two multiples of $6$ therefore it is a multiple of $6$