1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof about divisibility

  1. Jan 17, 2013 #1
    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. jcsd
  3. Jan 17, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    Think about the numbers modulo 171.
    Last edited: Jan 17, 2013
  4. Jan 17, 2013 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook