×

# Combinatorics #6

Suppose $$S=a_{1},a_{2},\cdots,a_{15}$$ is a set of $$15$$ distinct positive integers chosen from $$2,3,\cdots,2014$$ such that every two of them are coprime. Prove that $$S$$ contains a prime number. (Note: Two positive integers $$m,n$$ are coprime if their only common factor is $$1$$.

Note by Victor Loh
2 years, 11 months ago

Sort by:

Damn my first solution was lost in the preview...had to rewrite.

Note that two numbers are coprime if they have no alike prime factors. If we assume $$S$$ are all composite, then we can represent each $$a_i=p_i*q_i*k$$ where all $$p_i,q_i$$ are distinct primes and $$p_i\le q_i$$ Hence $$2014\ge a_i>p_i^2\Rightarrow p_i\le 43$$. Since $$43$$ is the 14th prime, but there are $$15$$ numbers, hence there must exists $$1\le r<s\le15$$ such that $$p_r=p_s$$ which is a contradiction. · 2 years, 11 months ago

You forgot that $$p_i=q_i$$ is a possibility. · 2 years, 11 months ago

I did specify that $$p_i\le q_i$$. Note that the intent for doing all this is to show that the smallest prime factor of each $$a_i$$ must be under $$43$$. · 2 years, 11 months ago

You can simply use logic to solve this. Assuming $$S$$ has no primes, the maximum number of distinct numbers it can contain is $$14$$. Logically thinking, for $$S$$ to contain as many numbers of possible, we would square prime numbers, thus maximising the number of prime factors as the prime factors of a prime squared would be itself only. We are given that the 15th prime is $$47$$ and $$47 \times 47$$ gives us $$2209$$ which is bigger than $$2014$$.

(Sorry if some of my reasoning is unclear) · 2 years, 11 months ago