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 $\displaystyle n^3+14n$ is divisible by 3. I am trying induction:

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

Inductive step:
$\displaystyle (n+1)^3+14(n+1)$
$\displaystyle = n^3+3n^2+17n+15$
$\displaystyle = (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:
$\displaystyle (n+1)^3+14(n+1)$
$\displaystyle = n^3+3n^2+17n+15$
$\displaystyle = (n+1)^2(n^2+2n+15)$
In problems like these, avoid your habit from algebra of always factoring everything completely:

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

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

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

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

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

3. Hello, horan!

I'll slightly modify your work . . .

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

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

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

Inductive step: $\displaystyle S(k+1)$

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

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

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

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

4. Hello, horan!

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

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

and $\displaystyle 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!