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

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.

• Note that the sum is $n(n+1)/2$ – J. W. Tanner Feb 13 '19 at 20:51
• A comment on consistency: why not get rid of $m$ and rewrite the top line $\frac n2\pmod n\quad2\mid n$? That way, there is an easy comparison between the two conditions $2\mid n$ and $2\nmid n$. – Théophile Feb 13 '19 at 20:52

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)$$

• I think you meant $mn+m$ – J. W. Tanner Feb 13 '19 at 21:27
• Oh thanks for that – JoseSquare Feb 13 '19 at 21:33

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

• Clever. +1 from me – J. W. Tanner Feb 13 '19 at 21:29

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