# Proving that every triangular number $\frac{k(k+1)}{2}$ has a remainder of $0$ or $1$ when divided by $3$

I need to show that every triangular number $\frac{k(k+1)}{2}$, where $k$ is a natural number, will have a remainder of either $0$ or $1$ when divided by $3$.

I was thinking of either considering the cases of when $k$ is an even and an odd number, or trying to show that the remainder cannot be $2$. However, I am not quite sure how to go from there.

Any ideas or hints would be great. Thanks!

• You only have to try 0, 1, 2 as it's under $\mathbb{F}_3$. – simonzack Mar 27 '15 at 13:12

JAck D'Aurizio's solution works fine, and is direct, but simonzack's comment points out a very straightforward general method that nearly always works. The key is:

If you have some expression involving $k$, and you are asked some question about the remainder when this expression is divided by 3, do not consider whether $k$ is even or odd. Instead, consider the remainder when $k$ is divided by 3.

In this case, the remainder when $k$ is divided by 3 is either 0, 1, or 2. Three cases is not too many to check by hand.

Suppose the remainder when $k$ is divided by 3 is 1. Then $k = 3j+1$ for some integer $j$, and then $$\frac{k(k+1)}2 = \frac{(3j+1)(3j+2)}2 = \frac{9j^2 + 9j + 2}2 = \frac12(9j^2+9j) +1.$$

The left-hand term, $\frac12(9j^2+9j)$, is a multiple of 3, so the remainder, when you divide the whole expression by 3, is 1.

Can you do the other two cases yourself?

Assume that $\frac{k(k+1)}{2}$ has remainder $2$. Then $4k(k+1)$ has remainder $1$, hence $(2k+1)^2$ has remainder $2$, that is impossible since $2$ is not a quadratic residue $\pmod{3}$.

Let $\,k(k\!+\!2) = 2n.\,$ We must show: $\,\overbrace{ 3\mid k(k\!+\!1)/2 = \color{#0a0}n}^{\large n\text{ has remainder } 0},\$ or  that $\ \overbrace{3\mid\color{#b0f}{n\!-\!1} = k(k\!+\!1)/2-1}^{\large n\text{ has remainder } 1}$

If $\smash[b]{\ \underbrace{3\mid k\ \ {\rm or}\ \ 3\mid k\!+\!1}}\$ then $\,3\mid k(k\!+\!1) =2n,\,$ $\rm\color{#c00}{so}$ $\,3\mid\color{#0a0} n.\$

Else $\ 3\mid k\!+\!2\$ so $\ 3\mid (\color{}{k\!+\!2})(k\!-\!1) = k(k\!+\!1)-2 = 2(n\!-\!1)\,$ $\rm\color{#c00}{so}$ $\,3\mid\color{#b0f}{n\!-\!1}$

Remark $\$ Twice above we have employed the $\rm\color{#c00}{property}$ $\ 3\mid 2x\,\Rightarrow\,3\mid x,\,$ by $\ x = 3x\!-\!2x$

If you know congruence arithmetic then the proof can be written more simply as follows.

${\rm mod}\ 3\!:\ \smash[b]{\underbrace{k\equiv \color{#c00}0\ \ {\rm or}\ \ \color{#0a0}2}}\,\Rightarrow\,\color{#c00}k(\color{#0a0}{k\!+\!1})(2^{-1})\equiv 0(2^{-1})\equiv 0\$

Otherwise, $\ k\equiv 1\,$ thus $\, k(k\!+\!1)(2^{-1})\equiv 1(2)(2^{-1})\equiv 1$