How to prove that $k^3+3k^2+2k$ is always divisible by $3$?

Question

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$?

$$k^3 + 3k^2 + 2k$$

Answer 1

Rewrite $k^3 + 3k^2 + 2k = k(k+1)(k+2)$. Since exactly one of the three factors must be divisible by 3, the product must also.

Answer 2

HINT: Try factoring!

Another hint:

$$k^3 + 3k^2 + 2k = k(k^2 + 3k + 2) = k (k+1)(k+2) $$ Thus, you expression is the product of three consecutive integers.

Answer 3

If $k$ is a multiple of $3$, then the statement is obviously true. Then suppose that $k$ is not a multiple of $3$. Since $k$ and $3$ are coprime, \begin{equation} k^2 \equiv 1\pmod 3 \end{equation} by Euler's theorem. Then \begin{equation} k^3+3k^2+2k \equiv 3k\equiv 0. \pmod 3 \end{equation} Therefore $k^3+3k^2+2k$ is divisible by $3$.

Answer 4

To check if values $p(k)$ of the polynomial $p$ with integer coefficients is divisible by $m$ for all integer $n$, you only to check that $$p(k) \equiv 0 \pmod m, \; \forall k \in {0,\ldots,n-1}\tag{1}$$ or equivalently $$m \mid p(k), \; \forall k \in {0,\ldots,n-1}$$

So if $p(k)=k^3+3k^2+2k$ we have

• $p(0)=0$ is divisible by $3$
• $p(1)=6$ is divisible by $3$
• $p(2)=24$ is divisible by $3$

and therefore $p(k)$ is divisible by $3$ for every integer $k$.

I think using $(1)$ is less elegant than the solution that factors the polynomial $p(k)$ but it shows a statement about the infinite set of integers that can be divided in finitely many cases that can be checked by a computer program.

Answer 5

Just to be different. If $k \in \mathbb Z$ then $k = 3m + i$ where $i = $ either $0, 1,$ or $-1$ and $m \in \mathbb Z$. So \begin{align*} k^3 + 3k^2 + 2k &=(3m + i)^3 + 2(3m + i)+ 3k^2 \\ &= 3^3m^3 + 3 \cdot 3^2m^2 \cdot i + 3 \cdot 3m \cdot i^2 + i^3 + 2 \cdot 3m + 2i + 3k^2 \\ &= i^3 + 2i + 3\big[3^2m^3 + 3^2m^2i + 3m \cdot i^2 + k^2\big] \end{align*}

Now $i^3 = i$ for $i = 0,1,-1$ so $i^3 + 2i = 3i$. So $$ k^3 + 3k^2 + 2k = 3\big[i + 3^2m^3 + 3^2m^2i + 3m \cdot i^2 + k^2\big]. $$

...

But seriously, factoring is the better way to do it.

Answer 6

Avoiding the factoring solution (since that's a special case - elegant, but not general):

We can ignore the $3k^2$ in $k^3+3k^2+2k$, so we just want to know if $k^3+2k=k(k^2+2)$ is divisible by $3$. Either $k$ is divisible by $3$, or it is not, in which case $k^2 \equiv 1 \mod 3$

Then $k^2+2\equiv 0 \mod 3$.

Answer 7

Alternatively, consider induction. The base case is clear. Assuming it holds for some $k$, $(k+1)^3+3 (k+1)^2+2 (k+1) = 3(k+2) (k+1) + (k^3+3 k^2+2 k)$ and so it holds for $k+1$.

Answer 8

Yet another approach: simply plugging in values gives

$$ 0^3 = 0 \mod 3 $$ $$ 1^3 = 1 \mod 3 $$ $$ 2^3 = 2 \mod 3 $$

In other words, $ k^3 = k \mod 3 $.

Therefore, $ k^3 + 3k^2 + 2k = 3k^2 + 3k = 0 \mod 3 $

Answer 9

Factorise $k^3 + 3k^2 + 2k = k(k+1)(k+2)$. Let $k\equiv 2 \mod 3$. Then $k+1\equiv 0 \mod 3$ and $k+2\equiv 1 \mod 3$. So, $k(k+1)(k+2)\equiv 0*1*2 \mod 3$. Therefore $k(k+1)(k+2)\equiv 0 \mod 3$.

Answer 10

Suppose we had to choose $3$ things out of $k+2$ things, there are $k+2$ ways of choosing the first one, $k+1$ ways of choosing the next, and $k$ ways of choosing the third. But we've overcounted by a factor of six, because any three things could be chosen in six different orders. So

$$(k+2)(k+1)k=k^3+3k^2+2k$$

divides by six and hence also by three.

Answer 11

Write the polynomial this way: \begin{align*} k^3 + 3k^2 + 2k &= (k^3 -3k^2 + 2k) + 6k^2 \\ &= k(k-1)(k-2) + 6k(k-1) + 6k \\ &= 6 \binom{k}{3} - 12 \binom{k}{2} + 6\binom{k}{1} \end{align*} But then it follows immediately that $$ k^3 + 3k^2 + 2k = 6 \left[ \binom{k}{3} - 2 \binom{k}{2} + \binom{k}{1} \right] $$ is divisible by $6$, and in particular divisible by $3$.

---

This isn't just a cute trick. It is actually a much more general approach that will solve all such problems.

The standard way of writing polynomials is in the basis $$ 1, x, x^2, x^3, \ldots $$ While this generally works fine, many discrete problems about polynomials (especially those about divisibility or integer-valued polynomials) are more natural when you use the following discrete basis of polynomials: $$ 1, \binom{x}{1}, \binom{x}{2}, \binom{x}{3}, \ldots $$ We have the following results:

Theorem 1. Every polynomial with rational coefficients, say $p(x) \in \mathbb{Q}[x]$, can be written uniquely as a finite linear combination (with rational coefficients) of the polynomials $\left\{\binom{x}{i} \right\}_{i \in \mathbb{N}}$.

Theorem 2. For $p(x) \in \mathbb{Q}[x]$, $p(n)$ is an integer for all $n \in \mathbb{Z}$ if and only if when it is written as a linear combination of the basis $\left\{\binom{x}{i} \right\}_{i \in \mathbb{N}}$, all coefficients are integers. (See integer-valued polynomial.)

An immediate corollary to Theorem 2 is that a polyomial $p(x)$ with integer coefficients is always divisible by $m$ if and only if when you write it in the $\binom{x}{i}$ basis, all of the coefficients are divisible by $m$. Hence, by a simple change-of-basis you can easily decide not just if $x^3 + 3x^2 + 2x$ is always divisible by $3$, but if any polynomial is always divisible by any integer. It's just a matter of writing it in a different basis than you are given.

---

Proof of Theorem 2. Since $\binom{n}{i}$ is always an integer for integer $n$ and $i$, the backward direction is clear. For the forward direction, consider a polynomial $p(x)$ with rational coefficients that maps integers to integers. Then apply Theorem 1 to obtain $$ p(x) = a_0 \binom{x}{0} + a_1 \binom{x}{1} + \cdots + a_k \binom{x}{k}. $$ Suppose towards contradiction that not all $a_i$ are integers. Then consider the first $i$ such that $a_{i}$ is not an integer. Since $\binom{i}{j} = 0$ for $j > i$, we have $$ p(i) = \underbrace{\underbrace{a_0 \binom{i}{0} + a_1 \binom{i}{1} + \cdots + a_{i-1} \binom{i}{i-1}}_{\in \mathbb{Z}} + a_i \binom{i}{i}}_{\in \mathbb{Z}} + 0 $$ implying that $a_i \binom{i}{i} \in \mathbb{Z}$. But $\binom{i}{i} = 1$, so $a_i \in \mathbb{Z}$, contradiction.

Answer 12

Even integer $k$ can be written as $3l+m$, $m\in\{0,1,2\}$. We can progressively eliminate the obvious: for instance $3k^2$. Remains $(3l+m)^3$ and $2(3l+m)$. Developping the first term, only $m^3$ remains. In the second term, only $2m$ remains. So we are left with $m^3+2m = m^3-m+(2m+m)$. Remains $m^3-m = m(m-1)(m+1)$, which are consecutive integers. So one of them is a multiple of $3$.

Some converse and related techniques are the Proof by infinite descent or Vieta jumping. Or an adaptation of Sherlock Holmes "when you have eliminated the impossible, whatever remains, however improbable, must be the truth"; here we have: "when you have eliminated the obvious, whatever remains, however simple, must be trivial".

Answer 13

Without noticing that the expression is factorisable into 3 consecutive numbers:

Define $a = k \;\text{mod}\;3$

$$(k^3 + 3k^2 + 2k) \;\text{mod}\;3 \\ = (k^3\;\text{mod}\;3 + 3k^2\;\text{mod}\;3 + 2k\;\text{mod}\;3) \;\text{mod}\;3 \\ = (a^3\;\text{mod}\;3 + 3a^2\;\text{mod}\;3 + 2a\;\text{mod}\;3) \;\text{mod}\;3$$

$a^3 \;\text{mod}\;3$:

1. If $a=1$, $a^3 = 1$.
2. If $a=2$, $a^3\;\text{mod}\;3=8\;\text{mod}\;3=2$.

So $a^3 \;\text{mod}\;3 = a$.

$3a^2\;\text{mod}\;3 = 0$

$2a\;\text{mod}\;3$:

1. If $a=1$, $2a\;\text{mod}\;3 = 2$.
2. If $a=2$, $2a\;\text{mod}\;3 = 4\;\text{mod}\;3 = 1$.

So $2a \;\text{mod}\;3 = -a\;\text{mod}\;3$.

$$(a + 0 + -a)\;\text{mod}\;3 = 0$$.

Answer 14

By Fermat's Little theorem $k^3\equiv k\pmod{3}$, therefore:

$$k^3+\underbrace{3k^2}_{\equiv 0}+\underbrace{2k}_{\equiv -k}\equiv k^3-k\equiv 0\pmod{3}$$