Find all interesting sets of p+2 integers where sums of p divide the rest

  • Level: Graduate 
  • Thread starter Thread starter newchie
  • Start date Start date
  • Tags Tags
    Primes Proof
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
5 replies · 4K views
newchie
Messages
19
Reaction score
0
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.
 
Physics news on Phys.org

Discussion

mathwonk said:
how interesting is this?
:))))

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?
 
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.
 
There should be an :applauding: smilie here. It took me some time, but I think I followed the whole thing. Nice!
 
Dodo said:
There should be an :applauding: smilie here. It took me some time, but I think I followed the whole thing. Nice!


I second that. :smile: