0
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ Note that the sum is $n(n+1)/2$ $\endgroup$ – J. W. Tanner Feb 13 '19 at 20:51
  • $\begingroup$ 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$. $\endgroup$ – Théophile Feb 13 '19 at 20:52
1
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ Clever. +1 from me $\endgroup$ – J. W. Tanner Feb 13 '19 at 21:29
0
$\begingroup$

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

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