1
$\begingroup$

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!

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

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?

$\endgroup$
5
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.