# How to prove that $k^3+3k^2+2k$ is always divisible by $3$? [closed]

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

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

-

## closed as off-topic by Silvia Ghinassi, T. Bongers, Frunobulax, wythagoras, probablymeFeb 4 at 21:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Silvia Ghinassi, T. Bongers, Frunobulax, wythagoras, probablyme
If this question can be reworded to fit the rules in the help center, please edit the question.

It is always divisible by 2, too. So it is always divisible by 6. – miracle173 Feb 4 at 13:25
Can someone make the title equation match the question equation? :-) – Hellion Feb 4 at 16:14

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.

-

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.

-

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.

-
I second that. Being clever is great, but it is also very useful to know how one can solve a problem if one does not have a clever idea. – Carsten S Feb 4 at 9:22
this approach holds even (especially) in situations when factoring comes up short – MichaelChirico Feb 4 at 13:07
+1 for this. It's exactly as Carsten S says--this is actually a much more general approach, and generality is more important than elegance! – 6005 Feb 4 at 15:58

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, $$k^2 \equiv 1\pmod 3$$ by Euler's theorem. Then $$k^3+3k^2+2k \equiv 3k\equiv 0. \pmod 3$$ Therefore $k^3+3k^2+2k$ is divisible by $3$.

-
Euler's theorem seems a bit overkill for the statement that modulo 3, $(\pm 1)^2 = 1$ ;-) – Steve Jessop Feb 4 at 12:10
If Euler's theorem did not come immediately to mind, you could note the quadratic term falls out since it has coefficient 3, and the two remaining are negative of each other mod 3 by Fermat's little theorem. – Colin McLarty Feb 4 at 13:31
If Euler's theorem did come to mind, the Fermat's Little Theorem also came to mind, and we have 3k^2 + 3k = 0 mod 3. – djechlin Feb 4 at 15:38

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$

-

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$.

-

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$.

-

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.

-
Isn't a bit confusing and unnecessary to use $i$ for something that not the imaginary number $i$? – snoram Feb 4 at 9:15
@snoram not in an obviously-not-complex domain like this. See how many times $i$ crops up with a meaning other than $\sqrt {-1}$ on the wikipedia page about summation, for example – AakashM Feb 4 at 9:52
@AakashM: The people that edit Wikipedia use it $\Rightarrow$ it is not unnecessary and confusing? – snoram Feb 4 at 10:05
@snoram I'm not asserting that. I'm saying that using $i$ for things other than $sqrt {-1}$ is completely standard practice, and is generally not found to be confusing. I've no idea what is or isn't 'unnecessary'. – AakashM Feb 4 at 10:13
I think stating "where $i = 0,1 , -1$" has to rule out any confusion. But even so $i$ is perhaps the must common indexing variable.Confusion is a minimal concern. Even $\pi$ is "overloaded" (en.wikipedia.org/wiki/Prime-counting_function). Personally I prefer to use $k$ for a "plus a constant" value as this is but $k$ was already in use. It never occurred to me it'd look like $i$ and had I, I might have considered $j$ but I don't think it can be considered a serious concern. No more than a treatise on carnivorous birds should be concerned about the religion symbolism of owls. – fleablood Feb 4 at 17:16

Write the polynomial this way: $$k^3 + 3k^2 + 2k = 6 \binom{k}{1} - 12 \binom{k}{2} + 6\binom{k}{3}$$ But then it becomes immediately obvoius that $$k^3 + 3k^2 + 2k = 6 \left[ \binom{k}{1} - 2 \binom{k}{2} + \binom{k}{3} \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.

-
I don't understand your proof of theorem 2, what if $i < k$? How then can you say that $p(i)$ is equal to that sum without the terms beyond $a_i$? – Brennan.Tobias Feb 4 at 19:07
@Brennan.Tobias I added a little clarification. The terms after $a_i \binom{i}{i}$ are all zero. – 6005 Feb 4 at 19:11
Thanks, That's a really elegant proof! – Brennan.Tobias Feb 4 at 19:19
This is a textbook example of a really good answer saving a ... not good question. – pjs36 Feb 4 at 19:30
@pjs36 Thanks :) – 6005 Feb 4 at 20:01

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}$$

-

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$.

-
This can also be done by taking either $k\equiv 1 \mod 3$ Or $k\equiv 0 \mod 3$. – sai saandeep Feb 4 at 14:26

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.

-

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".

-

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$.

# $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$$.

-