Show that $\frac{n(n+1)}{2} ≡ 0\mod n$ for $n$ an odd prime number.

Question

I need help to prove the following question.

I have thought about it, since $n$ is odd I can express it as $2k+1$.

I can also express $\frac{n(n+1)}{2} ≡ 0\mod n$ as $\frac{n(n+1)}{2} ≡ qn+0$.

I would appreciate any help to prove the problem.

Thanks!

score 2 · Answer 1 · answered Feb 22 '16 at 15:58

2

The prime part doesn't matter. If $n$ is odd, then $n+1$ is even and $\frac {n+1}2$ is an integer.

answered Feb 22 '16 at 15:58

Ross Millikan

But how do you know that the entire expression is divisible by $n$? Oh, sorry, of course, because dividing by $2$ has not "affected" the value of $n$. – barak manos Feb 22 '16 at 15:59
1

Because you get $n\cdot\text{integer}$. – Clement C. Feb 22 '16 at 15:59
1

@barakmanos: because it is $n$ multiplied by an integer. – Ross Millikan Feb 22 '16 at 15:59

score 1 · Answer 2 · answered Feb 22 '16 at 16:03

1

Indeed $n$ being odd one can write it as $n=2k+1$. And so we have

$${n(n+1)\over 2}=(2k+1)(k+1)=n(k+1)$$

And we have our result. We didn't need that $n$ is prime. The result is valid for any odd number.

answered Feb 22 '16 at 16:03

marwalix

Hi Marwalix, just to confirm my understanding does it mean that the final result is just expressing in the form of (n(n+1))/2 ≡ qn+0 when q is k+1. Hence, this would prove that (n(n+1))/2 ≡ 0 mod n ? – user292965 Feb 22 '16 at 16:24
Yes you're right – marwalix Feb 23 '16 at 08:00

score 0 · Answer 3 · answered Feb 22 '16 at 16:53

If we write $$\frac{n(n + 1)}{2} = qn,$$ then we are trying to show that for all odd prime $n,$ $q$ is an integer.

Working with this equation, we have $$n(n + 1) = 2qn$$ $$n + 1 = 2q$$ $$q = \frac{n + 1}{2}.$$

But since $n$ is odd (given), then $q$ is an integer. We have thus finished the proof.

score 0 · Answer 4 · answered Feb 22 '16 at 17:08

0

If $n$ is odd, the $n + 1$ is even. So $\frac{n(n+1)}{2} = n\frac{n+1}{2} = nk$ where $n+1 = 2k$ for some $k$ an integer (because $n + 1$ is even).

Likewise if $n$ is even then $\frac{n(n+1)}{2} = (n+1)\frac{n}{2}= (n+1)k \equiv 0 \mod (n+1)$.

answered Feb 22 '16 at 17:08

fleablood

4 Answers4