# Math Help - Divisibility by 9

1. ## Divisibility by 9

Prove that, for any positive integer $n$

$n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}$

is divisible by 9.

$\begin{bmatrix} x \end{bmatrix}$ denotes the integer part of $x$.

2. Please delete. Posted in wrong forum. Sorry :P

3. Check whether the given problem is divisible by 9 for n = 4 onwards.

4. Yes it is. But it comes to 0 for n=1,2,3.

5. Originally Posted by CuriosityCabinet
Prove that, for any positive integer $n$

$n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}$

is divisible by 9.

$\begin{bmatrix} x \end{bmatrix}$ denotes the integer part of $x$.

Try a case by case verification:

1.) $n\equiv0\bmod{3}\implies$ the equation becomes $n(n-1)(n-2) - 2n$

2.) $n\equiv1\bmod{3}\implies$ the equation becomes $n(n-1)(n-2) - 2(n-1)$

3.) $n\equiv2\bmod{3}\implies$ the equation becomes $n(n-1)(n-2) - 2(n-2)$

Now simplify each case and use Fermat's little theorem.

6. Originally Posted by CuriosityCabinet
Prove that, for any positive integer $n$

$n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3} \end{bmatrix}$

is divisible by 9.

$\begin{bmatrix} x \end{bmatrix}$ denotes the integer part of $x$.

Calculate $n(n-1)(n-2)=n(n-3n+2)=n^3-3n^2+2n$.
Any integer $n$ can be written in the form $\displaystyle{n=3[\frac{n}{3}]+r}$, where $r=0,1,$ or $2$. It follows that $\displaystyle{3[\frac{n}{3}]=n-r}$.

Now, simplifying, $n(n-1)(n-2) - 6 \begin{bmatrix} \frac{n}{3}\end{bmatrix}=n^3-3n^2+2n-2(n-r)=n^3-3n^2+2r$.

Consider three cases:
1. $n\equiv 0 \bmod 3$: $n^3-3n^2=n^2(n-3)$ and since $n$ is divisible by 3, $n^2$ is divisible by 9.

2. $n\equiv 1 \bmod 3$: $n^3-3n^2+2=(n-1)(n^2-2n-2)=(n-1)[(n-3)(n+1)+1]$, where $n-1\equiv 0 \bmod 3$ and $(n-3)(n+1)+1\equiv -2\cdot 2 +1\equiv 0 \bmod 3$. Then $(n-1)(n^2-2n-2)$ is divisible by 9.

3. $n\equiv 2 \bmod 3$: $n^3-3n^2+4=(n-2)^2(n+1)$, and since $n-2 \equiv 0 \bmod 3$ it follows that $(n-2)^2$ is divisible by 9.

For cases 1. and 2. I noticed that 1 and 2 are the roots, respectively, of the polynomials and then used Polynomial Division.