Let p be a prime. Let S be a set of (p-1) integers, none of which are divisible by p. Show that some subset of S has a sum that has a remainder of 1 when divided by p.

(The sum of a set is defined as the sum of the elements of the set)

(In reply to re(3): Yet another Erdos theorem by Richard)

Yes, you did clearly indicate that you had not solved the problem, I was just worried that you thought that the product-problem was somehow related to the sum-problem, which I don't believe is the case.

As far as the difficulty level goes, it is hard to judge the difficulty of a problem when you already know the solution.  Perhaps this should be a difficulty level 5 problem. 

By the way, I am proud to say that this is an original problem. 

Posted by David Shin on 2005-01-26 04:48:51