Waste less time on Facebook — follow Brilliant.

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
3 years ago

No vote yet
1 vote


Sort by:

Top Newest

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. Xuming Liang · 3 years ago

Log in to reply

@Xuming Liang You forgot that \(p_i=q_i\) is a possibility. Daniel Liu · 3 years ago

Log in to reply

@Daniel Liu 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\). Xuming Liang · 3 years ago

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 · 3 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...