# Pigeon Hole Principle - proof of d as a positive integer

Let $d$ be a positive integer and consider any set $A$ of $d+1$ positive integers. Show that there exists two different numbers $x, y\ \epsilon\ A$ so that $x \mod\ d = y \mod\ d$ and $x =/= y$.

Remainders after division by $d$ must fall in the range $0 ≤ r ≤ d − > 1$; there are precisely $d$ different remainders. By the pigeonhole principle, at least two of any collection of $d + 1$ integers must have the same remainder when divided by $d$.

I know I have to use the pigeon hole principle for this, but I'm unsure as to how to start this. Any help would be great

• HINT: What are the possible values of $x\bmod d$? How many of them are there? – Brian M. Scott Apr 22 '15 at 21:28
• There are only $d$ different equivalence classes modulo $d$. What you have is $d+1$ equivalence classes (one for each element of $A$), so two of them must be equal. – Uncountable Apr 22 '15 at 21:29
• @BrianM.Scott updated my post – user3434743 Apr 23 '15 at 19:19
• $Z_d$is a partition of Z in d classes and any integer must be in one of them. – Piquito Apr 23 '15 at 19:49