Let d be a positive integer. Show that among any group of d +1 (not necessary consecutive) integers, there are two with exactly the same remainder when divided by d.
i believe there is something missing from the question, or you're not describing something correctly. one thing i can see (i may be wrong) we have to have that , otherwise, we cannot show what we are being asked.
for the sake of illustration, let's say d = 1, that is a positive integer. so d + 1 would be 2. there is no guarantee, by the pigeonhole principle or otherwise, that any arbitrary group of two integers would have two elements that are congruent mod 4
when you divide an integer by some other integer, the remainder can range from zero right up to 1 less than the number you divided by: if you divide by 4, the possible remainders are 0, 1, 2 and 3. If you divide by 2, the possible remainders are 0 and 1, if you divide by 5, the possible remainders are 0,1,2,3, and 4. if you go any greater than this, you repeat this cycle. let's say you could have more remainders than this. let's say if you divide by 2, your possible remainders could be 0,1, and 2. 0 and 1 are fine, but if the remainder is 2, you could simply get another factor of 2 out of the original number and have a remainder of zero.
TPH used that principle. We have n + 1 integers being divided by n, so the possible remainders are 0, 1, 2, 3, ..., (n - 1), one less than the number we divided by. if you count starting from 0 up to (n - 1) you get n remainders. look at my illustrations above, you will find if you divide by 2 you have 2 possible remainders, if you divide by 5, you have 5 possible remainders. so here, we have n possible remainders. but there are (n + 1) integers, meaning when you get to the nth integer, you would have exhausted the n remainders, so the next (n + 1)th integer must reuse one of the remainders already used, so there will be two numbers with the same remainder when divided by n
see here for more on the Pigeonhole Principle
no, the remainders are the holes, and the integers are the pigeons
if you pick an integer and it has a remainder of 0 when divided by n, then you put it in the hole for 0, if it has a remainder of 1 when divided by n, you put it in the hole for 1, and so on. eventually, after n consecutive integers, you would have filled all the holes, and the last integer must be put into a hole that is already used. (if the integers are not necessarily consecutive, and it is the case that you haven't filled the holes by the nth integer, it simply means you already reused one of the holes at least once, so there are already at least two integers with exactly the same remainder)