Number theory question

1. Sep 20, 2011

AdrianZ

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. Sep 20, 2011

Robert1986

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.

3. Sep 20, 2011

AdrianZ

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.

4. Sep 20, 2011

Robert1986

OK, let $a_1,a_2,\ldots,a_n$ be the elements of your n-element set. Consider these sums:

$a_1 \equiv m_1 mod n$
$a_1 + a_2 \equiv m_2 mod n$
$\vdots$
$a_1 + a_2 + \cdots + a_n \equiv m_n mod n$

Now, what would it mean if one of the $m_i$'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 $a \equiv c mod n$ and $b \equiv c mod n$ what can you say about a-b mod n?

5. Sep 20, 2011

AdrianZ

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.

6. Sep 20, 2011

Robert1986

Beautiful!

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook