# Divisibility by 9

• August 26th 2010, 03:14 AM
CuriosityCabinet
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$.

• August 26th 2010, 03:26 AM
CuriosityCabinet
Please delete. Posted in wrong forum. Sorry :P
• August 26th 2010, 03:36 AM
sa-ri-ga-ma
Check whether the given problem is divisible by 9 for n = 4 onwards.
• August 26th 2010, 03:38 AM
CuriosityCabinet
Yes it is. But it comes to 0 for n=1,2,3.
• August 26th 2010, 07:30 AM
chiph588@
Quote:

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.
• August 28th 2010, 05:18 AM
melese
Quote:

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.