Prove the sum from $1$ to $n$ is congruent to half $n$ or $0$ for even or odd values of $n$

Question

I am trying to prove this for any natural number $n$:

$$ \sum_{k=1}^{n} k \equiv \left\{ \begin{array}{ll} \frac{n}{2} \pmod n & \quad 2\mid n \\ 0 \pmod n & \quad 2\nmid n \end{array} \right. $$

So essentially the sum of all natural numbers 1 to $n$ is congruent to either 0 when $n$ is odd or half of $n$ for even $n$ values. I haven't worked much with sums within the congruence relationship so I'm not sure where to start on this one.

Answer 1

Since is well known that $\sum_{k=1}^{n} k = \frac{n}{2} (n+1)$, then if $n$ is even so $n=2m$, then the sum is $m(n+1)$ which is $mn +m \equiv m \;(mod \;n)$. If $n$ is odd, then $(n+1)$ is even, so there exist $c\in \mathbb{N}$ such $c=\frac{n+1}{2}$, so then the sum will be $c*n \equiv 0 \; (mod \; n)$

Answer 2

Note that $$ 1+2+\cdots+n $$ is also equal to $$ 0+1+2+\cdots+n. $$ The latter sum can be rearranged as $$ (0+n)+(1+(n-1))+(2+(n-2))+\cdots\qquad\qquad(*) $$ where every written summand is equal to $n$.

But what is the last summand in (*)?.

If $n$ is odd, taking $\{0,1,2,...,n\}$ in pairs will exhaust the set, so that the total sum is a multiple of $n$, hence congruent to $0\bmod n$.

But if $n=2m$ is even, after taking pairs you are left with just $m$, so the total is congruent to $m\bmod n$.

---

I think this method could be called "baby Gauss $+0$".

Answer 3

It's well known that $\sum_{i=1}^n i = \frac {n(n+1)}2,$ which means $2|n(n+1),$ which, if you are naive, might seem like a coincidence. (very naive). But if $n$ is even then $2|n$ and $\frac {n(n+1)}2 = \frac n2(n+1)$ and if $n$ is odd then $n+1$ is even and $2|(n+1)$ and $\frac {n(n+1)}2 = n\frac {n+1}2$.

So the result follows pretty simply:

If $n$ is odd, then $\frac {n(n+1)}2 = n\frac {n+1}2 \equiv 0 \pmod n$.

If $n$ is even, then $\frac {n(n+1)}2 = \frac n2(n+1) = m(n+1)\equiv m* 1 \equiv m \pmod n$

....

As a side note I think there are 3) types of people.

1) Those who learn $\sum_{i=1}^n i = \frac {n(n+1)}2$ because someone told them.

2) Those who figure on their own that

$N = 1 + 2 + ....... + n$

$N = n + (n-1) + ..... + 1$

$2N = (n+1) + (n+1) + ..... + (n+1)$

$N = \frac {n(n+1)}2$

And

3) Those who figure out on their own that

$N = \underbrace{1 + \underbrace{2 + \underbrace{....}+(n-1)}+1}=$

$\begin{cases}\frac n2\times (n+1)&n \text{ is even}\\\frac {n-1}2\times (n+1) + \text{middle of }(1...n)=\frac{n-1}2\times (n+1) + \frac {n+1}2 = \frac n2(n+1)_{\text{a fraction times an even number}}&n\text{ is odd}\end{cases}$