Show that given a set of positive n integers, there exists a non-empty subset whose sum is divisible by n This is the question I've run into: Show that given a set of  positive n integers, there exists a non-empty subset whose sum is divisible by  n
I'm having trouble understanding how they came to the conclusion

the part that I'm having trouble understanding is how subtracting the two subsets results in a sum that's divisible by n given that the two subsets have the same remainder
 A: Let $p<q$, if $S_p = \sum_{i=1}^p s_i \equiv r \pmod{n}$
and $S_q = \sum_{i=1}^q s_i \equiv r \pmod{n}$
then we have $S_q-S_p=\sum_{i=p+1}^q s_i \equiv r-r \equiv  0 \pmod{n}$
where we have use the property that if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then we have $a-c \equiv b-d \pmod{n}$ 
If you are not familiar with modulo arithmetic, view it as if $a = nk+r$ and $c = nt+r$, then $a-c = n(k-t)$.
A: Via modular arithmetic this is very easy, and something you can check (if you're familiar with this). Otherwise, one can show the following result via the division algorithm (i.e. just straight division with quotient and remainder):

If $a$ and $b$ have the same remainder when divided by $n$, then $a-b$ is divisible by $n$.

The proof is as follows. Let $r$ be the common remainder of $a$ and $b$ when divided by $n$. The division algorithm gives integers $q,p$ such that $a=qn+r$ and $b=pn+r$. Thus, we get $$a-b=(qn+r)-(pn+r)=(qn-pn)+(r-r)=(q-p)n$$
so $n$ divides $a-b$.
Note that the above result is more general, and can be applied to your situation by having $a=S_j$ and $b=S_i$. It doesn't really matter that the $S_i$ and $S_j$ are sums of integers when applying the statement I just proved; as far as we care they are just some integers $a$ and $b$.
