We select n + 1 different integers from the set { 1, 2, ···, 2 n }. Provethat there will alwaysbe two among the selected integers whose largestcommon divisor is 1.

See answer below

Step-by-step explanation:

From the set

{1,2,3,4 ... 2n} we have 2n numbers in total, n are odd and n are even, therefore for a sample of n+1 numbers, we have at least 1 even number and 1 odd number.

Then

it the set includes 1, the largest common divisor is 1 for 1 and the other numbers

if the set includes 3, there will be always a number that is not divisible by 3. Even we construct a set of n+1 numbers that are multiple of 3, the largest number would be 3 * (n+1) = 3*n+3 > 2*n (out of bounds), therefore we are forced to take other number that is not divisible by 3 → the largest common divisor of that number with 3 is 1

If the set includes any other prime number → the largest common divisor of that with any other is 1

For the remaining odd numbers N, they can be factorised into other 2 odd common divisors N₂ and n₂:

N = N₂*n₂, since n₂ ≥ 2 → N₂ < N

then the even N₂ also should be contained in the set

therefore also for N₂

N = N₃*n₃ → N₃ < N₂

therefore if we continue, we would obtain a number even Nn that has no smaller common divisors → since we cannot take all the multiples of N min (because Nmin * (n+1) = Nmin*n+Nmin > 2*n for Nmin≥2) → there is at least a number in the sample of n+1 integers whose largest common divisor is 1