I have been trying an approach that doesn't seem to work. I remember solving a problem:
Prove that in a set of n integers there is a subset such that the sum of its elements is divisible by n.
Oooh! I remember seeing something like this from an Olympiad problem. I can't quite remember, but it was a little stronger than the problem smaia gave us. In the Olympiad it was also to prove a subset of n integers divisible by n, but that time there was only 2n-1 numbers to choose from, 1 less than what smaia gives us.
modulo n, you can have n-1 lots of a number that is x mod n, and n-1 lots of a number that is y mod n, but then as soon as you have a number that is z mod n, a number can be divisible by n by taking the z mod n number and a configuration of the x mod n and y mod n numbers.
Thus the maximum numbers you can have to avoid divisibility is n-1 + n-1 or 2n-2. If we have 2n, we are above this maximum.
I am happy with this, other people won't be.
Ah yes. I can do the second part of David's way. I can do it for 2n-1 numbers as well.
The proposition is that among a set of 2n-1 integers, there are always n such that the sum of them is divisible by n.
Suppose this is true for n=p and n=q (p,q prime). Let us look at when n=pq.
Then we will have a set of 2pq-1 integers which i will call A, where we are trying to find pq of them whose sum divides pq.
Take 2p-1 integers from A. Because the proposition is proven for n=p, we can find p integers, whose sum is divisible by p. Remove these p numbers from A. Clearly we can do this with the set remaining, etc.
After we have found 2q-2 distinct subsets of A, each of p elements and the sum being divisible by p, we will have 2pq-1-(2pq-2p)=2p-1 numbers remaining in A. And again, as the proposition is proven for n=p, we can again choose a subset.
So we can find 2q-1 distinct subsets of A, each of p elements and each with a sum divisible by p. Let the sums of each of these subsets by S(1), S(2), S(2)... S(2q-1).
Consider the set {S(1), S(2), ... S(2q-1)} Clearly there are 2q-1 elements, and because the proposition is proven for n=q, we can choose q of these sums, and the total is divisible by q.
Now replace each of the sums with the p original elements from A. Look at the sums we have chosen. We have ended up choosing pq elements, and the sum of them is divisible by q and since each of the 'sub-sums' is divisible by p, the total is divisible by p. As p and q are prime, the pq elements have a total divisible by pq.
Therefore, if the proposition is true from primes p,q, it is true also for pq.
Looking over the explanation, I realise it may be long-winded and unclear. Someone fix things up for me please!
As for proving it for all primes, I will start on fiddling with modular arithmetic, and possible FLT, I am so sure FLT has something to do with all this.
EDIT: Err, this only proves it for all square-free numbers
EDIT: Scrap that, p and q don't actually have to be prime, do they?