Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof for primes help!

  1. Mar 25, 2012 #1
    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. jcsd
  3. Mar 29, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    how interesting is this?
  4. Mar 29, 2012 #3

    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?
  5. Mar 29, 2012 #4
    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.
  6. Mar 29, 2012 #5
    There should be an :applauding: smilie here. It took me some time, but I think I followed the whole thing. Nice!
  7. Mar 29, 2012 #6

    I second that. :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook