Maths Olympiad Prep

Library / /27 of 54

Number theory Difficulty 6.1 National olympiad Prove it China

Let S={1,2,,2005}S = \{1, 2, \dots, 2005\}. If there is at least one prime number in any subset of SS consisting of nn pairwise coprime numbers, find the minimum value of nn.

Solution

First we prove n16n \ge 16. In fact, let
A0={1,22,32,52,,412,432}, A_0 = \{1, 2^2, 3^2, 5^2, \dots, 41^2, 43^2\},
where the members in A0A_0, other than 11, are the squares of prime numbers not greater than 4343. Then A0SA_0 \subseteq S, A0=15|A_0| = 15 and the numbers in A0A_0 are pairwise coprime but A0A_0 contains no prime number. Thus n16n \ge 16.

Next we show that for arbitrary ASA \subseteq S with n=A=16n = |A| = 16, if the numbers in AA are pairwise coprime, then AA must contain a prime number.
In fact, if AA contains no prime number, denote A={a1,a2,,a16;a1<a2<<a16}A = \{a_1, a_2, \dots, a_{16}; a_1 < a_2 < \dots < a_{16}\}. Then there are two possibilities.

(1) If 1A1 \notin A, then a1,a2,,a16a_1, a_2, \dots, a_{16} are composite numbers. Since (ai,aj)=1(a_i, a_j) = 1 (1i<j161 \le i < j \le 16), the prime factors of aia_i and aja_j are pairwise distinct. Let pip_i be the smallest prime factor of aia_i. We may assume that p1<p2<<p16p_1 < p_2 < \dots < p_{16}, then
a1p1222,a2p2232,,a15p152472>2005, a_1 \ge p_1^2 \ge 2^2,\quad a_2 \ge p_2^2 \ge 3^2,\quad \dots,\quad a_{15} \ge p_{15}^2 \ge 47^2 > 2005,
it leads to a contradiction.

(2) If 1A1 \in A, let a16=1a_{16} = 1, a1,a2,,a15a_1, a_2, \dots, a_{15} are composite numbers. By the same assumption and argument of (1), we have a1p1222a_1 \ge p_1^2 \ge 2^2, a2p2232a_2 \ge p_2^2 \ge 3^2, ,a15p152472>2005\dots, a_{15} \ge p_{15}^2 \ge 47^2 > 2005. Again, it leads to a contradiction.

From (1) and (2), AA contains at least one prime number, i.e. when n=A=16n = |A| = 16, the conclusion is true. Thus, the minimum number of nn is 1616.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.