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

• It is always divisible by 2, too. So it is always divisible by 6. Feb 4 '16 at 13:25
• Can someone make the title equation match the question equation? :-) Feb 4 '16 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. Feb 4 '16 at 9:22
• this approach holds even (especially) in situations when factoring comes up short Feb 4 '16 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 '16 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, \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$.

• Euler's theorem seems a bit overkill for the statement that modulo 3, $(\pm 1)^2 = 1$ ;-) Feb 4 '16 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. Feb 4 '16 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. Feb 4 '16 at 15:38

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.

• 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$? Feb 4 '16 at 19:07
• @Brennan.Tobias I added a little clarification. The terms after $a_i \binom{i}{i}$ are all zero.
– 6005
Feb 4 '16 at 19:11
• Thanks, That's a really elegant proof! Feb 4 '16 at 19:19
• This is a textbook example of a really good answer saving a ... not good question. Feb 4 '16 at 19:30
• @pjs36 Thanks :)
– 6005
Feb 4 '16 at 20:01

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$

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

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

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$? Feb 4 '16 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 Feb 4 '16 at 9:52
• @AakashM: The people that edit Wikipedia use it $\Rightarrow$ it is not unnecessary and confusing? Feb 4 '16 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'. Feb 4 '16 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. Feb 4 '16 at 17:16

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$. Feb 4 '16 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$$.