Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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

share|improve this answer
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

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)

share|improve this answer
...if n is odd. –  Jonas Meyer Oct 18 '10 at 1:06

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.