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)

Since we are working modulo p here, instead of considering a set of p-1 integers none of which is divisible by p, we can instead consider an ordered set, or sequence, of p-1 numbers, with repetitions allowed, and with the numbers drawn from {1,...,p-1}.  The problem is to show that any such sequence always contains a subsequence that sums to a number congruent to 1 mod p. I have verified that this is true for p <= 5.

For p <= 5 I find that (and I conjecture the same for all p), there is always a subsequence that, modulo p, sums to any given number in {0,...,p-1}, if we include the empty subsequence with sum 0. One approach thus seems to be to somehow show (by some kind of counting argument, perhaps) that, modulo p, at least p noncongruent values always appear in the collection of subsequence sums of any given sequence of p-1 numbers drawn from {1,...,p-1}.

Posted by Richard on 2004-12-31 18:10:49