Homework Help: discrete math

Posted by thisha on Wednesday, November 29, 2006 at 10:27pm.

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.

discrete math - MathMate, Monday, May 9, 2011 at 5:29pm
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.

Answer this Question

Related Questions

math, algebra - 2a+2ab+2b I need a lot of help in this one. it says find two ...
math - there are three consecutive positive integers such that the sum of the ...
Discrete Math - Theorem: For every integer n, if x and y are positive integers ...
discrete math - Could someone help me with this induction proof. I know its true...
Math - What is the smallest of 3 consecutive positive integers if the product of...
Math - What is the smallest of 3 consecutive positive integers if the product of...
algebra2 - Two consecutive positive integers have the property that one integer ...
Discrete Math - Could someone help me with this induction proof. I know its true...
math - there are 8 consecutive integers that add up to 31. Only two of the ...
MATH - Find the only positive integer whose cube is the sum of the cubes of ...

For Further Reading

First Name:
School Subject:
Answer: