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\).

## Comments

Sort by:

TopNewestDamn 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. – Xuming Liang · 2 years, 9 months ago

Log in to reply

– Daniel Liu · 2 years, 9 months ago

You forgot that \(p_i=q_i\) is a possibility.Log in to reply

– Xuming Liang · 2 years, 9 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\).Log in to reply

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) – Charlton Teo · 2 years, 9 months ago

Log in to reply