# Homework Help: Proof about divisibility

1. Jan 17, 2013

### cragar

1. The problem statement, all variables and given/known data
Show that in any set of 172 integers there must be a pair whose
difference is divisible by 171. Is the result true if the word
difference is replaced by sum.
I think it should say distinct integers
3. The attempt at a solution
I think I should start by partitioning the integers into segments
from 1 to 171 and then multiples of 171 like n171
I guess you would have a case where some of the integers could be
multiples of 171 and then their difference would be divisible by 171.
Or you would have them scattered in between some multiple
of 171 , but we have 172 of them and there are only 170 numbers in between
any multiple of 171 so their should exist a pair whose difference is a multiple of 171.
is this on the right track, i need o quantify this a little more.

2. Jan 17, 2013

### Dick

Think about the numbers modulo 171.

Last edited: Jan 17, 2013
3. Jan 17, 2013

### LCKurtz

I think you have a good idea there. You might quantify it more by thinking about the equivalence relation on the integers given by $n\sim m$ if $n =m\text{ mod } 171$. Then consider the equivalence classes $[0],[1],...,[170]$.

 Dang! Dick beat me to it.