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.
Printable View
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 thatQuote:
Originally Posted by Discrete
, 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
Are you sure your problem isn't 'd' instead of 4?.
"Let d be a positive integer. Show that among any group of d+1 (not necessary consecutive) integers, there are two with the same remainder when divided by d".
Givenintegers which are the "pigeons". Let the sets
be the remainders upon division by
. Since there are
Sorry guys I revised the question, there are some typo's there it should be divided by d
Yes, TPH's solution is valid for the revised question. he (and galactus) read through the lines and figured that's what you were really askingQuote:
Originally Posted by Discrete
Quote:
Originally Posted by Jhevon
I still don't get what TPH is saying, is the set {0}, {1}, ... {n-1} the remainder? if yes then where is the same remainder?
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.Quote:
Originally Posted by Discrete
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
gotcha jhevon's, I got it a bit more clear now.. so the remainder here can be represented as the pigeons right? and n+1 is the hole/cage of the pigeon?
no, the remainders are the holes, and the integers are the pigeonsQuote:
Originally Posted by Discrete
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)