# Divisibility by 9

• Aug 26th 2010, 03:14 AM
CuriosityCabinet
Divisibility by 9
Prove that, for any positive integer $\displaystyle n$

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

is divisible by 9.

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

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

Originally Posted by CuriosityCabinet
Prove that, for any positive integer $\displaystyle n$

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

is divisible by 9.

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

Try a case by case verification:

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

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

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

Now simplify each case and use Fermat's little theorem.
• Aug 28th 2010, 05:18 AM
melese
Quote:

Originally Posted by CuriosityCabinet
Prove that, for any positive integer $\displaystyle n$

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

is divisible by 9.

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

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

Now, simplifying, $\displaystyle 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. $\displaystyle n\equiv 0 \bmod 3$: $\displaystyle n^3-3n^2=n^2(n-3)$ and since $\displaystyle n$ is divisible by 3, $\displaystyle n^2$ is divisible by 9.

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

3. $\displaystyle n\equiv 2 \bmod 3$: $\displaystyle n^3-3n^2+4=(n-2)^2(n+1)$, and since $\displaystyle n-2 \equiv 0 \bmod 3$ it follows that $\displaystyle (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.