Prove that $ n^3 + 5n$ is divisible by 6 for all $n\in \textbf{N}$ [duplicate]

$n^3+5n=n(n^2+5)$. One is odd and the other is even so 2 divides it.

$n^3+5n=n(n^2+5)\equiv n(n^2+2)\bmod 3$, so:

• if $n\equiv0 \bmod 3$ then $3$ divides it.

• if $n\equiv1$ or $-1 \bmod 3$, then $n^2\equiv1 \bmod 3$, so $3|n^2+2$.

$2$ and $3$ divide it, so $6$ divides it.

We prove that $ n^3 + 5n $ is divisible by 6 for all $ n \in \textbf{N} $.

Base case: Observe that if $ n = 1 $, then $ n^3 + 5n = 1 + 5 = 6 $.

So the base case holds.

Inductive step: Assume that $ k^3 + 5k $ is divisible by 6 for some $ k\in\textbf{N} $.

We show that $ (k+1)^3 + 5(k+1) $ is divisible by 6.

Since 6 divides $ k^3 + 5k $, it follows that $ k^3 + 5k = 6q $ for some integer $ q $.

Obverse that

$ (k+1)^3 + 5(k+1) = k^3 + 3k^2 + 3k + 1 + 5k + 5 = k^3 + 3k^2 + 8k+ 6 $

$ = 6(q+1) + 3k^2 + 3k $.

We break this up into 2 cases to consider odd and even values of $ k $:

Case 1. Suppose $ k $ is even. Then $ k=2w $ for some integer $ w $. Thus

$ 6(q+1) + 3k^2 + 3k =6(q+1) + 3(4w^2)+3(2w) = 6(q+1) + 6(2w^2) + 6w $

$ = 6(q+2w^2+w+1) $.

Case 2. Consider $ k$ is odd. Then $ k =2v + 1 $ for some integer $ v $. Then

$ 6(q+1) + 3k^2 + 3k = 6(q+1) + 3(2v+1)^2 + 3(2v+1) $

$ = 6(q+1) + 3(4v^2+4v+1) + 6v+3 = 6(q+1) + 6(2v^2+2v)+6(v+1)$

$ = 6 (2v^2+3v+2+q) $.

So the claim holds for all $ n \in \textbf{N} $.

Hint $\displaystyle \ \ n^3\!+5n = n^3\!-\!n+6n = (n\!+\!1)n(n\!-\!1) + 6n = \color{#c00}6{ {n\!+\!1\choose 3}} + \color{#c00}6n\ $ is divisible by $\,\color{#c00}6$

Alternatively show $\,(n\!+\!1)n(n\!-\!1)\,$ is divisible by both $2$ and $3$. Generally a sequence of $\,k\,$ consecutive integers contains a multiple of $\,k\,$ (pigeonholes being remainders mod $\,k).$

More generally $\ 2p\mid n^p-n\ $ for odd primes $p,\,$ since $\ p\mid n^p-n\ $ by little Fermat, and it's divisible by $2$ since $\,n^p$ and $\,n\,$ have equal parity. Even more generally

Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For $\rm\:1 < e,m\in \Bbb N\:$ we have $$\rm \forall\, n\in\Bbb Z\!:\ m\mid n^e\!-n\ \iff\ m\ \ is\ \ squarefree,\ \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid m$$

For a proof see this answer. Your case is $\,\rm\,e,m = 3,6\,$ and, indeed, $2\!-\!1,\,3\!-\!1\mid 3\!-\!1.$

All numbers are either even or odd. So if n is odd, $2|n^3+5n$ as $n^3$ leaves remainder $1$ when divided by 2 and $5n$ leaves remainder $1$. For even 'n' the case is trivial.

And all numbers can classified in $3k,3k+1,3k+2$ forms. So n=3k+1, the remainder of $n^3$ when divided by 3 is 1 and for $5n$ it will be $2$ and $2+1=3$.

And for $n=3k+2$, the $n^3$ leaves remainder 2 when divided by 3 and $5n$ leaves remainder $1$ when divided by 3, hence proved. The case is trivial for n=3k.

Thus as the number $n^3+5n$ is always divisible by 2 & 3. thus it is always divisible by 6.