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

  • $\begingroup$ HINT: What are the possible values of $x\bmod d$? How many of them are there? $\endgroup$ – Brian M. Scott Apr 22 '15 at 21:28
  • $\begingroup$ 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. $\endgroup$ – Uncountable Apr 22 '15 at 21:29
  • $\begingroup$ @BrianM.Scott updated my post $\endgroup$ – user3434743 Apr 23 '15 at 19:19
  • $\begingroup$ $Z_d$is a partition of Z in d classes and any integer must be in one of them. $\endgroup$ – Piquito Apr 23 '15 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.