Erdös and Posa: coprime

Paul Erdös asked the 12-yr old Hungarian Math prodigy Posa:

Take 51 numbers from 1 to 100, why there will be at least 2 numbers relative prime?

Posa took few coffee cups, imagine 50 of them.
1. Put consecutive numbers (1, 2) in 1st cup, (3, 4) in 2nd cup,… (99, 100) in 50th cup.
2. Take out all odd numbers (1, 3, 5, k…, 99) from each cup => total 50 odd numbers
3. Take 51st number from any remaining (say kth) cup => the number = k+1
4. (k+1) & k from (step 2) co-prime    [QED]

Two consecutive numbers co-primes

Prove by reductio ad absurdum:
Let a, b consecutive numbers: a – b = 1
Assume a, b not co-prime,
There is g.c.d. (a, b) = c divides both a, b
=> a = c.a’, b = c.b’
=> a – b = c(a’-b’)
Since a-b = 1 (consecutive),
c(a’-b’) = 1
=> c |1 impossible
=> a , b must be co-prime [QED]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s