# Sum of primes up to p is multiple of p?

Is the sum of primes up to p a multiple of p?

i.e Is 1+2+...+p divisible by p and how would you prove it?

-

What you wrote is not the sum of the primes up to $p$. 1 is not prime, and the meaning of your ellipsis is unclear. Based on one possible interpretation, a counterexample is that 2 does not divide $1+2$. Based on another, a counterexample is that 3 does not divide $2+3$.

However, if $p$ is an odd number, and in particular if it is a prime other than 2, then $p$ divides the sum of the first $p$ positive integers, because this sum is $p\cdot\frac{p+1}{2}$.

-
On the other hand, for $p>2$ the sum of all integers from $1$ to $p$ is a multiple of $p$. –  lhf Oct 18 '10 at 1:03
Yes, I added that simultaneously with your comment. –  Jonas Meyer Oct 18 '10 at 1:04

$\begin{array}{rcl}\rm{\bf Hint}\quad\quad\ \ S &=&\rm 1 \ \ \ +\ \ \: 2\ \ \ \ +\ \:\cdots\ +\ p\!-\!1\ +\ p \\ \rm S &=&\rm p \ \ +\ p\!-\!1\ +\,\ \cdots\ +\,\quad 2\ \ \ +\ \ 1\\ \hline \\ \rm Adding\ \ \ \ 2\: S &=&\rm p\ (p+1)\end{array}$

A famous legend says Gauss used this trick to quickly compute $1+2+\:\cdots\:+100\$ in grade school.

This trick of pairing up reflections around the average value is a special case of exploiting innate symmetry - here a reflection or involution. It's a ubiquitous powerful technique, e.g. see my post on Wilson's Theorem and it's group theoretic generalization.

-
Not what was asked. See Jonas Meyer's answer. –  lhf Oct 18 '10 at 1:20
@lhf: No, this is the only sensible interpretation of what was asked. The other possible interpretation doesn't make sense for two reasons: the sum includes 1, which isn't prime and, moreover, this other interpretation has trivial counterexamples. –  Bill Dubuque Oct 18 '10 at 21:31
Thanks for that link on the Gauss legend, it is interesting. I agree that the most probable interpretation of this confused question is that $p$ divides the sum of the first $p$ positive integers. It isn't clear whether fmunshi wanted an explanation of the formula for the sum, but if so then this post would certainly be helpful. I don't understand why this post received a downvote. –  Jonas Meyer Oct 18 '10 at 23:05
@Jonas: I'm glad to hear that you found the link interesting. I too am perplexed by the downvote. Perhaps someone objects to me frequently exploiting those poor little symmetries. –  Bill Dubuque Oct 18 '10 at 23:19

Or if by the ellipsis you mean the sum of naturals up to p, it is true and not just for primes. The sum of naturals up to n is $n*(n+1)/2$, which can be proved by induction, and is divisible by n. (as commented, only if n is odd)

-
...if n is odd. –  Jonas Meyer Oct 18 '10 at 1:06