Question 1: Let d be a positive integer and consider any set A of d+1 positive i

Question

Question 1: Let d be a positive integer and consider any set A of d+1 positive integers. Show that there exists two different numbers x, y∈A so that x mod d=y mod d and x not equal to y.

Question 2: 1. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two consecutive numbers
2. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two numbers x, y so that gcd(x, y) = 1
Question 1: Let d be a positive integer and consider any set A of d+1 positive integers. Show that there exists two different numbers x, y∈A so that x mod d=y mod d and x not equal to y.

Question 2: 1. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two consecutive numbers
2. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two numbers x, y so that gcd(x, y) = 1
Question 2: 1. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two consecutive numbers
2. Say that you take n+ 1 numbers out of 1,2, . . . ,2n. Show that there will be two numbers x, y so that gcd(x, y) = 1

Explanation / Answer

1. There are only d remainder classes modulo d.Since there are d+1 positive integers,by Pigeon Hole Principle there should be two positive integers which have same remainder modulo d

Hence the problem

2. (i) Divide the numbers 1,2,...,2n in to n disjoint sets {1,2}, {3,4},...{2n-1,2n}.Since n+1 numbers are selected there is atleast one set from which two are selected by PHP

Hence there will be two consecutive numbers.

(ii) By part i there are two consecutive numbers in the n+1 numbers selected.These have gcd 1.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.