Let $A \subset \mathbb Z$ with $|A| = 17$. Prove there are distinct $a, b \in A$ such that $16$ divides $a − b$

Question

Let $A \subset \mathbb Z$ with $|A| = 17$. Prove there are distinct $a, b \in A$ such that $16$ divides $a − b$.

I'm not sure where to take this question and where to begin. If anyone could direct me in the right direction or show me the direct proof I'd appreciate it

Answer 1

There are 17 elements in A. Let r be the remainder left when the elements are divided by 16. Thus the r can be one of 16 values from 0 to 15. Since there 17 elements, atleast two elements must have the same r by pidgeon hole principle. Let a and b be these elements. So a (mod 16) = r and b (mod 16) = r. (a - b) (mod 16)=0 Hence its divisible by 16