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 Yet another Erdos theorem by e.g.)

I still don't see how the paper you cite actually leads to a solution of the given problem, but I think I now see what you are alluding to. In the paper a result is mentioned that Erdos attributed to Andrew Vazsonyi and Marta Sved according to Aigner and Ziegler in "Proofs from the Book, 2nd Ed., Chapter 21, Section 3. This result is the following.

Lemma: Suppose we are given n integers a_1,...,a_n which need not be distinct. Then there is always a set of consecutive numbers a_(k+1),a_(k+2),...,a_l whose sum is a multiple of n.

We will here mirror the proof that Aigner and Ziegler show for the lemma in order to try to prove the result of the given problem. First, however, we ring in some well-known facts concerning finite fields of a prime number of elements.

The following theorem is a well-known result on the finite fields GF(p) of p numbers, p a prime. We suppose henceforth that p denotes a prime number.

Theorem: The multiplicative group of GF(p) is cyclic of order p-1.

The theorem implies that there is at least one element r of GF(p) such that r^(p-1) = 1 but  r^k ~= 1 for positive whole k < p-1. Such an r is called a primitive element. Thus the nonzero elements of GF(p) all are powers of any primitive element r.

In GF(p), any p-1 numbers n_1,...,n_(p-1), which need not be distinct, can be written as powers of some primitive element r, viz. r^m_1,...,r^m_(p-1). Consider the sequence n_1,n_1*n_2,n_1*n_2*n_3,...,n_1*n_2*n_3*...*n_(p-1) which is the same as r^m_1,r^(m_1+m_2),...,r^(m_1+m_2+...+m_(p-1)). In the sequence 0,m_1,m1+m_2,...,m_1+m_2+...+m(p-1) there must be two members that are in the same residue class mod p-1 since the sequence has a total of p members. Subtracting the earlier from the later of these gives some value m_i+...+m_j that is a multiple of p-1. Then n_i*...*n_j=r^(m_i+...+m_j)=1 so a subsequence product of the original sequence n_1,...,n_(p-1) is equal to 1 in GF(p), i.e., is 1 modulo p in the integers mod p. This is the result of the given problem, except that it is for products rather than sums.

 

Posted by Richard on 2005-01-25 20:58:35