Prove there are $2$ numbers in a set whose difference is a multiple of $9$?

Question

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

Answer 1

Guide:

• 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?