Suppose $S$ is a set of $10$ integers (any integers at all). Prove that there are a pair of numbers in $S$ whose difference is a multiple of $9$; i.e. Prove that there exists $a, b \in S$ such that $a \neq b$ and $a − b$ is a multiple of $9$. (Hint: Apply the Pigeonhole Principle to the potential remainders of elements of $S$ with respect to division by $9$. You may assume that given any integer $n \in \mathbb{Z}$, there exists an integer $k$ and $r$ such that $n = 9k + r$, where $0 \le r < 9$; i.e. this $r$ value is the remainder of the number when classically divided by $9$.)

I am very overwhelmed with this question and don't even know where to start. I understand the concept of the pigeonhole principle but I do not understand how it related here.. Any help greatly appreciated



  • If two numbers share the same remainder when they are divided by $9$, then the difference is divisible by 9.
  • How do you ensure that you can find such pair of numbers?

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.