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(2): Yet another Erdos theorem by David Shin)

Thanks for the hints.  I think I quite clearly indicated that I had not solved your problem, but rather the same problem for products rather than sums.  An exponent that is 0 mod p-1 gives a power of a primitive root that is congruent to 1 mod p.  My point is that I can only believe that e.g. is mistaken about the paper he cited being applicable to your problem, but that it can be construed to apply to the similar result for products instead of sums. I note that e.g. has yet to reply to either of my queries concerning his post.

Your problem is an important one, mathematically, I believe, much more so than many of the difficulty level 4 problems seen on perplexus.  I look forward to seeing the official solution and will continue thinking about it, but doubt I will discover it's "secret" any time in the forseeable future.  The simple proof of the lemma in my comment is one that would elude me for all eternity, I'm afraid, and the solution your problem may well be just as elusive, at least for me. 

Posted by Richard on 2005-01-26 00:04:28