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

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.

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

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.