Use the division algorithm to prove that 3|(n³ + 2n) for all n ∈ ℕ

I can do it by induction, thanks to the wonderful people of this website, but I'm not sure how to do it by the Division algorithm. Can anyone help me? I think I can show how 3 divides 2n, but I'm not sure how to show that 3 divides n³.


Note that $$n^3+2n=3n^2+n(n-1)(n-2),$$ hence it would suffice to show that $$3\mid 3n^2\qquad\text{and}\qquad 3\mid n(n-1)(n-2),$$ to deduce that indeed, $$3\mid n^3+2n.$$ Can you proceed?


This is less elegant and less fun than Did's answer, but you could try using the Division Algorithm. The Division Algorithm says that you can find integers $q$ and $r$ such that $n=3q+r$ and $r$ is $0$, $1$, or $2$. So there are three cases: (i) $n=3q+0$, (ii) $n=3q+1$, and (iii) $n=3q+2$. In each case you can show that $n^3+2n$ is divisible by $3$.

For instance, here's how you can do case (iii): if $n=3q+2$ then $$n^3+2n=n(n^2+2)=n([3q+2]^2+2)=n(9q^2+12q+6),$$ and so $$\frac{n^3+2n}3=n(3q^2+4q+2)$$ is an integer, showing that $n^3+2n$ is divisible by $3$.


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

See The product of n consecutive integers is divisible by n factorial