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 p <= 5 and more by Richard)

I think that you can even eliminate 1 from the set of remainders and just need to show that with the p-1 numbers drawn from {2,...,p-1} you can achieve a sum equal to 1 mod p.

Other than that observation I have nothing to offer. 

Posted by ken on 2005-01-02 00:26:14