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]

The "Book"

Paul Erdös liked to talk about 'The Book', in which God maintains the perfect proofs for mathematical theorems (& he 'peeped' 1,000 from there).

Paul Erdös

[caption id="" align="alignright" width="246"] head of Paul Erdös, Budapest fall 1992 (Photo credit: Wikipedia)[/caption]

Paul Erdös

1. The mathematician could carry his equations in his head, like a chess master playing blindfolded.
2. "A mathematician is a machine for turning coffee into theorems."