# Mod operator and divisibility by $3$?

I wanted to prove that $n(n+1)(2n+1)$ is always divisible by three, for this I used the following approach:

$n = 0, 1\pmod2$

for $n = 0$; $$n(n+1)(2n+1) \equiv 0\pmod3$$

for $n = 1$; $$n(n+1)(2n+1) \equiv 0\pmod3$$

But now I am unsure if this the correct way of doing because of the following eg:

Let $k = \text{an odd number}\equiv 1\mod3$

for $k = 1$; $2k + 1 \equiv 0\pmod3$, therefore for every odd number $2k + 1$ is divisible by $3$, but this is not true.

So my question is the approach I am using to prove $n(n+1)(2n+1)$ divisible by $3$ is wrong or only the second example is wrong?, and why?

-
Why do you look at $n$ mod 2 at the beginning, when what you're interested in is $n(n+1)(2n+1)$ mod 3? Where does the 2 come from? –  Ben Millwood Jun 3 '12 at 9:00

Your first mistake is at the very beginning, when you split into two cases according as $n$ is even or odd. You’re looking at divisibility by $3$, not by $2$, so it’s unlikely to matter whether $n$ is even or odd; you should be looking at the cases $n\equiv 0\pmod3$, $n\equiv 1\pmod3$, and $n\equiv 2\pmod3$. Here’s most of a table showing the congruence classes mod $3$ of the expressions involved.

$$\begin{array}{rcc} n\bmod3:&0&1&2\\ (n+1)\bmod3:&1&2&0\\ (2n+1)\bmod3:&1\\ \hline \big(n(n+1)(2n+1)\big)\bmod3:&0&&0 \end{array}$$

With what I’ve already filled in, you can see that $n(n+1)(2n+1)$ is divisible by $3$ when $n\equiv 0,2\pmod3$; if you finish filling in the table, you can finish the proof.

-
Thank you, Actually I was quite unsure about using mod, and you really helped me in understanding it. –  Kartik Anand Jun 3 '12 at 9:05

Every number $n$ is congruent to $0$, $1$, or $2$ mod $3$.

If $n \equiv 0 \pmod 3$, then $3 \mid n$.

If $n \equiv 1 \pmod 3$, then $2n \equiv 2 \pmod 3$ which implies $2n + 1 \equiv 3 \pmod 3$ which implies $2n + 1 \equiv 0 \pmod 3$.

If $n \equiv 2 \pmod 3$, then $n + 1 \equiv 3 \pmod 3$ which implies $n + 1 \equiv 0 \pmod 3$.

Hence for all for all $n$, $n(n + 1)(2n + 1)$ is divisible by $3$.

-
Note that $2\equiv -1\bmod 3$, so we have $$n(n+1)(2n+1)\equiv n(n+1)(-n+1)\equiv-n(n+1)(n-1)\bmod 3.$$ Of course, $3$ divides one of the numbers $n-1$, $n$ and $n+1$.
Writing $$n(n+1)(2n+1)=6\binom{n}{1}+18\binom{n}{2}+12\binom{n}{3}\tag{1}$$ we see that $n(n+1)(2n+1)\equiv0\pmod{6}$.