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: Mod problem - computer sci math course

  1. May 2, 2013 #1
    1. The problem statement, all variables and given/known data
    Let b be a positive integer and consider any set S of b+1 positive integers.
    Show that there exists two different numbers x, y ∈ S so that x mod b = y mod b

    2. Relevant equations

    3. The attempt at a solution
    Pretty stumped. I tried for a while to use different values of b but I soon realized that this could lead to pretty much infinite amounts of any different positive integers in my set.
  2. jcsd
  3. May 2, 2013 #2
    So you have b + 1 different numbers. Take any of them, say x, you can obtain z, the remainder of x's division by b, so you have a map x -> z in this way. To how many different z's, at most, can you map the original set?
  4. May 2, 2013 #3


    Staff: Mentor

    This problem uses the "pigeon-hole" principle. Here you have b slots (0, 1, 2, 3, ..., b-2, b-1) and b+1 numbers. Is there any way the b+1 numbers can go into the slots without at least one duplication?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted