Question

Prove that if we select 101 integers from the set S = {1,23, ..., 200}, there exist m, n in the selection where gcd(m,n) = 1

It's about Pigeonhole principle, but I really have no idea how to start?
any hint? :)

Answer 1

are you missing a comma?
should be gcd (m,n) = 1

Answer 2

if you pick two multiples of 2, then gcd (m,n) is not 1
if you pick two multiples of 3 , same deal

Answer 3

so in the worst case scenario, imagine you picked all multiples of some number ,
try to imagine that (its horrible)

Answer 4

yes.. it should be gcd(m,n)..., I've revised it...

Answer 5

so for instance, suppose you picked
{ 2,4,6,8,10,12.....198,200 } any two numbers in this set , gcd (m,n) is not 1. can be 2 or greater

Answer 6

this is the worst case scenario, do you see why?
what if you picked
{3,6,9,12,15,...198} , but thats not 101 numbers thats like not even close, maybe 66 numbers

Answer 7

hello?

Answer 8

the member of the set {2,4,6,8,...,200} and {3,6,...,198} are not 101,

Answer 9

I can't get your point... :(

Answer 10

any time you have a set of multiples the gcd will not be 1. so you have to show you have in your set two numbers which are not multiples of each other

Answer 11

{2,4,6,8...200} has 100 numbers, and that means if you add 1 more number, it cannot be a multiple of 2 . That number whatever it is , will be relatively prime. QED

Answer 12

hhmm..
I see...,
thank you... :)