Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this question

closed as off-topic by Silvia Ghinassi, T. Bongers, Frunobulax, wythagoras, probablyme Feb 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

14 Answers 14

up vote 40 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
6  
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, \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$.

share|cite|improve this answer
    
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 $

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
    
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
1  
@AakashM: The people that edit Wikipedia use it $\Rightarrow$ it is not unnecessary and confusing? – snoram Feb 4 at 10:05
2  
@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.

share|cite|improve this answer
    
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
1  
@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
1  
@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}$$

share|cite|improve this answer

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

share|cite|improve this answer
    
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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.