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
add comment

3 Answers

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
add comment

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
5  
...if n is odd. –  Jonas Meyer Oct 18 '10 at 1:06
add comment

$\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
1  
Not what was asked. See Jonas Meyer's answer. –  lhf Oct 18 '10 at 1:20
1  
@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
1  
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
add comment

Your Answer

 
discard

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.