# Proof for primes help!

1. Mar 25, 2012

### newchie

Would like to see a proof for the following question.

Let p be a prime number. Define a set interesting if it has p+2 (not necessarily distinct) positive integers such than the sum of any p numbers is a multiple of each of the other two. Find all interesting sets.

2. Mar 29, 2012

### mathwonk

how interesting is this?

3. Mar 29, 2012

### dodo

))

If one such collection is 'interesting', such as {1,1,1,1,3} for p=3, then any scaled-up version is also 'interesting': {2,2,2,2,6}, {10,10,10,10,30}, or the like. So call these collections 'primitive' (there goes another wordo) if they don't have any common factor among all numbers (the numbers could still be non-coprime when taken pairwise).

The issue is that, if you try with a computer, the only 'primitive' collections appear to be: A) the "all ones" collection, (p+2 ones), or B) the "almost all ones" (p+1 ones and one 'p'). For example, for p=3, you find only {1,1,1,1,1} and {1,1,1,1,3} (assume the order is irrelevant, otherwise place the '3' in any of the 5 possible positions).

It's expensive to try with the computer for any but small numbers, so the issue is: is this the only solution, of is any other possible for larger numbers?

4. Mar 29, 2012

### Norwegian

The only interesting primitive sets are {1,1,1,...,1} and {p,1,1,...,1}.

Let {x1,...,xp+2} be interesting and primitive, and let Sk=(Ʃxi) - xk.

First observe that if one number, say xk, is divisible by p, then all other xi are congruent Sk modulo p. (Since xk|Sk-xi.)

Conclude that at most one of the xi are divisible by p.

For i≠j, we have Sj-xi=aixj, and this equation summed over all i (with i≠j), gives pSj=axj.
In particular, since xj|pSj and xj|p(Sj-xi), we must have xj|pxi for all i and j.

Conclude that all xi not divisible by p must be equal, and if any xj is divisble by p, it must be p times as much.

5. Mar 29, 2012

### dodo

There should be an :applauding: smilie here. It took me some time, but I think I followed the whole thing. Nice!

6. Mar 29, 2012

### epsi00

I second that.