If $n$ is a positive integer prove that $1+2+3+\cdots+(n-1)$ is congruent to $0\mod n$ if and only if $n$ is odd I am stuck with this question. I know I need a formula from calculus but I can't remember which one. How should I get started with it?
Thank you!
 A: The statement "if and only if" implies that you need to prove the statement in the forward and backward directions. So forward means "if $1+ 2 + 3 + \cdots + (n-1) \equiv 0 \pmod n,$ then $n$ is odd. To get started, note that $$1+ 2 + 3 + \cdots + (n-1) = {1\over2}n(n-1).$$ Suppose towards a contradiction that $n$ is even, or in other words, $n=2m$, where $m\in\mathbb N$. Then $${{1\over2}n(n-1) \over n} = {{1\over2}(2m)(2m-1) \over 2m} = {2m-1\over2},$$ but clearly $2m-1$ is odd, so the divisibility does not happen.
Now we want to do the reverse direction (i.e., "If $n$ is odd, then ${n(n-1)\over2}\equiv0 \pmod n.$"). Suppose that $n = 2m-1$, where $m\in\mathbb N$. Then $${{{1\over2}n(n-1)}\over n} = {1\over2}(n-1) = {1\over2}(2m-1-1) = {1\over2}(2m-2) = {2\over2}(m-1) = m-1.$$ It is clear that $m-1$ is an integer, and therefore ${1\over2}n(n-1) \equiv 0\pmod n.$
A: We can pair up the numbers into chunks which add up to $n$, as $(1, n-1)$, $(2, n-2)$, and so on up to $(\frac{n-1}{2}, \frac{n+1}{2})$ (if $n$ is odd) or we're left with a single $\frac{n}{2}$ in the middle if $n$ is even. [For example, if $n=6$, we have $(1,5), (2,4), 3$; if $n=7$, we have $(1,6), (2,5), (3,4)$.]
Therefore the sum is congruent to $\frac{n}{2}$ mod $n$ if $n$ is even, and to $0$ if $n$ is odd.
A: $1 + 2 + 3 + .....+ (n-1) = n(n-1)/2$.
Proposition: 
$n(n-1)/2$  is $0$  mod $n$ iff  $n$ is odd.
$\Rightarrow$:
1) Assume $n(n-1)/2$ is divisible by $n$, then
$n(n-1)/2 = s × n$, where $s$ is a positive integer.
$(n-1)/2 = s$, and finally $n= 2s + 1$, an odd number.
$\Leftarrow$:
2) Assume $n$ is odd:
Then $(n-1)$ is even, and $(n-1)/2 = r$, a positive integer.
We have $n(n-1)/2 = r×n$, hence $n$ divides $n(n-1)/2$.
