# Thread: [SOLVED] should be really simple... prove that n^3+14n is divisible by 3

1. ## [SOLVED] should be really simple... prove that n^3+14n is divisible by 3

I'm probably just being dumb now, but I cannot seem to prove that $n^3+14n$ is divisible by 3. I am trying induction:

Base case: $n=1$. Then 1+15=15, which is divisible by 3.

Inductive step:
$(n+1)^3+14(n+1)$
$= n^3+3n^2+17n+15$
$= (n+1)^2(n^2+2n+15)$

But then from here, I'm stuck. Any suggestions?

EDIT: this is for all ints >= 0.

2. Originally Posted by horan
Inductive step:
$(n+1)^3+14(n+1)$
$= n^3+3n^2+17n+15$
$= (n+1)^2(n^2+2n+15)$
In problems like these, avoid your habit from algebra of always factoring everything completely:

$n^3+3n^2+17n+15$

$=n(n^2+3n+17)+15$

By inductive hypothesis, $3\mid n\Rightarrow n=3p,\;\exists p\in\mathbb{Z}$ so we have

$n(n^2+3n+17)+15 = 3p(n^2+3n+17)+3\cdot5 = 3(pn^2+3pn+17p+5)$

$=3q,\;q=pn^2+3pn+17p+5\in\mathbb{Z}\text.$

3. Hello, horan!

I'll slightly modify your work . . .

Prove that: . $n^3+14n$ is divisible by 3.

Verify $S(1)\!:\;\;1^3 + 14(1) \:=\:15$ ... divisible by 3.

Assume $S(k)\!:\;\;k^3 + 14k \:=\:3a\;\text{ for some integer }a$

Inductive step: $S(k+1)$

. . $(n+1)^3+14(n+1) \;=\;n^3+3n^2+17n+15$

. . $= \;n^3 + 3n^2 + (14n + 3n) + 15 \;=\;(n^3 + 14n) + (3n^2 + 3n + 15)$

. . $= \;\underbrace{n^3 + 14n}_{\text{This is }3a} + \underbrace{3(n^2 + n + 5)}_{\text{a multiple of 3}}$

Therefore, $S(k+1)$ is divisible by 3.
. . The inductive proof is complete.

4. Hello, horan!

Note that $14\equiv-1\pmod3.$

Hence $n^3+14n=n(n^2+14)\equiv n(n^2-1)\pmod3$

and $n(n^2-1)=(n-1)n(n+1)$ is divisible by 3 because it’s the product of 3 consecutive integers.

5. ah, that helps a lot. thanks!