discrete math

let d be a positive integer. Show that among any group of d+19not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d.

The possible values of the remainders are 0, 1, 2, ...d-1. So there are a total of d different remainders, but you have d + 1 numbers.

1. 👍 0
2. 👎 0
3. 👁 351
1. cont'd
So by the Pigeon hole theorem, there are at least two numbers with the same remainders when divided by d.

Note: four and a half years too late, but someone searching for the Pigeon hole theorem may find it useful.

1. 👍 1
2. 👎 0
posted by MathMate

Similar Questions

1. math, algebra

2a+2ab+2b I need a lot of help in this one. it says find two consecutive positive integers such that the sum of their square is 85. how would i do this one i have no clue i know what are positive integers.but i don't know how to

asked by sana on January 26, 2007
2. math

What is the smallest of three consecutive integers if the sum of the smaller two integers is equal to 177 less than four times the largest? Note: Consecutive integers are integers that come one after the other. For example: -3, -2

asked by Joshua pouncy on September 14, 2016
3. math

What is the smallest of three consecutive integers if the sum of the smaller two integers is equal to 177 less than four times the largest? Note: Consecutive integers are integers that come one after the other. For example: -3, -2

4. math

What is the smallest of three consecutive integers if the sum of the smaller two integers is equal to 177 less than four times the largest? Note: Consecutive integers are integers that come one after the other. For example: -3, -2

asked by James Hockery on October 2, 2016

find 3 consecutive integers such that the product of the second and third integer is 20 Take three integers x, y, and z. The for xyz, we want y*z = 20 The factors of 20 are 20*1 10*2 5*4. 20*1 are not consecutive. 10*2 are not

asked by chrisw on January 31, 2007
6. MAth

In a set of five consecutive positive even integers, the ratio of the greatest integer to least integer is 2 is to 1. If these integers are arranged from lowest to highest, which is the middle integer in the list?

asked by john on April 12, 2017
7. math

there are three consecutive positive integers such that the sum of the squares of the smallest two is 221. write and equation to find the three consecutive positive integers let x= the smallest integer

asked by eddy on October 30, 2012
8. algebra1

Find to consecutive integers that the sum of 3 times the first integer and 6 times the second integer is 24. Define the variabls you use. If somebody can show me how to work this out, I will be very greatful for the help?

asked by Malik on March 23, 2007