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!
 A: 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}$.
A: 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?
A: 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$
