Proof of Divisibility in Sets of Integers

[cragar]

Homework Statement

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

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.

 

[Dick]

Homework Statement

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

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.

Think about the numbers modulo 171.

 

[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]$.

[Edit] Dang! Dick beat me to it.