1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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