# Mod problem - computer sci math course

1. May 2, 2013

### TheRascalKing

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 diﬀerent 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. May 2, 2013

### voko

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?

3. May 2, 2013

### 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?