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

Number theory question

  1. Sep 20, 2011 #1
    1. The problem statement, all variables and given/known data
    Suppose n is a natural number and A is a subset of natural number with n elements. Prove that a subset of A exists that the sum of its elements is dividable by n.

    3. The attempt at a solution
    well, This problem is harder than I can solve it. I first tried to use the pigeonhole principle to prove the existence of such a subset of A. well, It wasn't easy to prove it that way as I thought. so, now I feel that I'm stuck and have no idea of how to solve it. Any ideas?
  2. jcsd
  3. Sep 20, 2011 #2
    You're on the right track with PHP. How many congruancy classes are there modulo n? Think about this for a bit, and I have another hint if you need one.
  4. Sep 20, 2011 #3
    I've already thought about the number of congruency classes a lot. There are n congruency classes of modulo n ([0],...,[n-1]). In fact the Euclidean algorithm of division forces that. but the question is still so confusing. so another hint would be appreciated.
  5. Sep 20, 2011 #4
    OK, let [itex]a_1,a_2,\ldots,a_n[/itex] be the elements of your n-element set. Consider these sums:

    [itex]a_1 \equiv m_1 mod n[/itex]
    [itex]a_1 + a_2 \equiv m_2 mod n[/itex]
    [itex]a_1 + a_2 + \cdots + a_n \equiv m_n mod n[/itex]

    Now, what would it mean if one of the [itex]m_i[/itex]'s were 0? OK, now what if none of them are 0? How many congruancy classes does this leave? How many sums are there above? If a,b,c are integers and [itex] a \equiv c mod n[/itex] and [itex]b \equiv c mod n[/itex] what can you say about a-b mod n?
  6. Sep 20, 2011 #5
    well, if one of them is zero, we're done. if none of them is zero, then we'll have n-1 congruency classes and n such sums. that would mean that two of these sums should be in the same congruency class. therefore if we subtract those two from each other we'll have a new sum that is congruent to 0 modulo n and we're done.

    Thanks for the help.
  7. Sep 20, 2011 #6
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook