Maths Olympiad Prep

Library / /36 of 38

Number theory Difficulty 7.7 National olympiad, round 2 Prove it China

Suppose a set SS satisfies the following conditions:
(1) every element in SS is a positive integer and not greater than 100100;
(2) for any two different elements aa and bb in SS, there is an element cc in SS such that the greatest common divisor of aa and cc is equal to 11, and the greatest common divisor of bb and cc is also 11; and
(3) for any two different elements aa and bb in SS, there is an element dd, which is different from aa and bb, such that the greatest common divisor of aa and dd, and that of bb and dd are greater than 11.

Find the maximum number of elements in SS.

Solution

The maximum number of elements is 7272.

A positive integer not greater than 100100 can be written as
n=2a13a25a37a411a5q, n = 2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdot 7^{a_4} \cdot 11^{a_5} \cdot q,
where qq is a positive integer and not divisible by 22, 33, 55, 77 and 1111, and a1,a2,a3,a4a_1, a_2, a_3, a_4 and a5a_5 are nonnegative integers.

We pick out those positive integers nn with just one or two nonzero among a1,a2,a3,a4a_1, a_2, a_3, a_4 and a5a_5 to form set SS. In this case, SS contains 5050 even numbers (2,4,,982, 4, \ldots, 98 and 100100) except the following seven: 2×3×52 \times 3 \times 5, 22×3×52^2 \times 3 \times 5, 2×32×52 \times 3^2 \times 5, 2×3×72 \times 3 \times 7, 22×3×72^2 \times 3 \times 7, 2×5×72 \times 5 \times 7 and 2×3×112 \times 3 \times 11; 1717 odd numbers that are multiples of three (i.e. 3×1,3×3,,3×333 \times 1, 3 \times 3, \ldots, 3 \times 33), 77 odd numbers with the least prime divisor 55 (i.e. 5×1,5×5,5×7,5×11,5×13,5×175 \times 1, 5 \times 5, 5 \times 7, 5 \times 11, 5 \times 13, 5 \times 17 and 5×195 \times 19), 44 odd numbers with the least prime divisor 77 (i.e. 7×1,7×7,7×117 \times 1, 7 \times 7, 7 \times 11 and 7×137 \times 13), and the prime number 1111.

Consequently, SS contains (507)+17+7+4+1=72(50-7)+17+7+4+1=72 numbers totally.

In what follows, we will prove that SS constructed above satisfies the given condition.

Obviously, it satisfies condition (1).

For condition (2), we note that, at most, four prime divisors among 2,3,5,72, 3, 5, 7 and 1111 will occur in [a,b][a, b]. We write the prime which does not occur as pp. Obviously, pSp \in S and
(p,a)(p,[a,b])=1,(p,b)(p,[a,b])=1. (p, a) \le (p, [a, b]) = 1, \\ (p, b) \le (p, [a, b]) = 1.
Hence, we take c=pc = p.

For condition (3), we take the least prime divisor of aa as pp and the one of bb as qq when (a,b)=1(a, b) = 1. It is easy to see that pqp \ne q and p,q{2,3,5,7,11}p, q \in \{2, 3, 5, 7, 11\}. Hence pqSpq \in S, and
(pq,a)p>1 and (pq,b)q>1. (pq, a) \ge p > 1 \text{ and } (pq, b) \ge q > 1.
Being coprime to each other for aa and bb ensures that pqpq is different from aa and bb. Thus we take d=pqd = pq.

When (a,b)=e>1(a, b) = e > 1, we take pp as the least prime divisor of ee, and qq as the smallest prime number satisfying q[a,b]q \nmid [a, b]. It is easy to see that pqp \ne q, and pp and q{2,3,5,7,11}q \in \{2, 3, 5, 7, 11\}. Hence pqSpq \in S, and
(pq,a)(p,a)=p>1,(pq,b)(p,b)=p>1. (pq, a) \ge (p, a) = p > 1, \\ (pq, b) \ge (p, b) = p > 1.
q[a,b]q \nmid [a, b] ensures that pqpq is different from aa and bb. Thus, we take d=pqd = pq.

In what follows, we prove that the number of elements in SS, which satisfies the conditions described in the problem, will not be greater than 7272.

Obviously, 1S1 \notin S. For arbitrary two prime numbers pp and qq which are both greater than 1010, since the least number which is not prime to neither pp nor qq is pqpq, it must be greater than 100100. So we know, according to condition (3), that there is at most one among 2121 prime numbers between 1010 and 100100 (11,13,,89,9711, 13, \ldots, 89, 97), occurring in SS. We write the set consisting of all natural numbers not greater than 100100 except 11 and the above-mentioned 2121 prime numbers as TT, and there are 7878 numbers in the set. We can conclude that there are at least 77 numbers in TT are not in SS. Thus SS contains at most 787+1=7278 - 7 + 1 = 72 elements.

i. When a prime number pp is greater than 1010 and belongs to SS,

every number in SS can only have 2,3,5,72, 3, 5, 7 and pp as its least prime divisor. By condition (2), we have the following conclusions.

① If 7pS7p \in S, because {2×3×5,22×3×5,2×32×5,7p}\{2 \times 3 \times 5, 2^2 \times 3 \times 5, 2 \times 3^2 \times 5, 7p\} contains all the least prime divisors, we know from condition (2) that 2×3×5,22×3×52 \times 3 \times 5, 2^2 \times 3 \times 5 and 2×32×52 \times 3^2 \times 5 do not belong to SS. If 7pS7p \notin S, noting 2×7p>1002 \times 7p > 100, but pSp \in S, so from condition (2) we know that 7×1,7×7,7×117 \times 1, 7 \times 7, 7 \times 11 and 7×137 \times 13 do not belong to SS.

② If 5pS5p \in S, then 2×3×72 \times 3 \times 7 and 22×3×72^2 \times 3 \times 7 do not belong to SS. If 5pS5p \notin S, then 5×15 \times 1 and 5×55 \times 5 do not belong to SS.

2×5×72 \times 5 \times 7 and 3p3p do not belong to SS at the same time.

2×3p2 \times 3p and 5×75 \times 7 do not belong to SS at the same time.

⑤ If 5p,7pS5p, 7p \notin S, then 5×7S5 \times 7 \notin S.

When p=11p = 11 or 1313, from ①, ②, ③ and ④, we can get at least 3,2,13, 2, 1 and 11 numbers in TT respectively which do not belong to SS, and in total 77 numbers. When p=17p = 17 or 1919, from ①, ② and ③, we can get at least 4,24, 2 and 11 numbers in TT respectively, which do not belong to SS and in total 77 numbers. When p>20p > 20, from ①, ② and ③, there are at least 4,24, 2 and 11 numbers in TT respectively, which do not belong to SS and in total 77 numbers also.

ii. If there is no prime number greater than 1010 belonging to SS, then the least prime numbers in SS can only be 2,3,52, 3, 5 and 77. Hence, each of the following 77 pairs of numbers can not belong to SS at the same time:
(3,2×5×7),(5,2×3×7),(7,2×3×5),(2×3,5×7),(2×5,3×7),(2×7,3×5),(22×7,32×5). (3, 2 \times 5 \times 7), (5, 2 \times 3 \times 7), (7, 2 \times 3 \times 5), (2 \times 3, 5 \times 7), (2 \times 5, 3 \times 7), (2 \times 7, 3 \times 5), (2^2 \times 7, 3^2 \times 5).
Thus, there are at least 77 numbers in TT that are not in SS.

Consequently, the answer for this problem is 7272.

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.