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
asked by thisha
  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

Respond to this Question

First Name

Your Response

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

    asked by Madison Joe on September 14, 2016
  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
  5. quad. eq.

    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
  9. geometry!!! please help me!!!!

    Determine the least positive integer n for which the following condition holds: No matter how the elements of the set of the first n positive integers, i.e. {1,2,…n}, are colored in red or blue, there are (not necessarily

    asked by sanji on May 8, 2013
  10. maths

    the non- decreasing sequence of odd integers {a1, a2, a3, . . .} = {1,3,3,3,5,5,5,5,5,...} each positive odd integer k appears k times. it is a fact that there are integers b, c, and d such that, for all positive integers n, añ =

    asked by fui on November 11, 2016

More Similar Questions