Maths Olympiad Prep

Library / /7 of 27

Number theory Difficulty 6.4 National olympiad Find the answer

Let SS be the set of positive integers. For any aa and bb in the set we have GCD(a,b)>1GCD(a, b)>1. For any aa, bb and cc in the set we have GCD(a,b,c)=1GCD(a, b, c)=1. Is it possible that SS has 20122012 elements?

*

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine if there is a set S S consisting of 2012 positive integers such that:

1. For any two distinct elements a a and b b in S S , their greatest common divisor GCD(a,b)>1 \text{GCD}(a, b) > 1 .
2. For any three distinct elements a a , b b , and c c in S S , their greatest common divisor GCD(a,b,c)=1 \text{GCD}(a, b, c) = 1 .

The challenge is to construct such a set S S of 2012 elements.

### Construction of the Set S S

Consider the prime numbers p1,p2,,p2012 p_1, p_2, \ldots, p_{2012} . We can define each element ai a_i of the set S S as the product of two distinct primes from our chosen set of 2012 primes. Specifically, let:

ai=pip2012 a_i = p_i \cdot p_{2012}

for each i=1,2,,2011 i = 1, 2, \ldots, 2011 . Let the final element be:

a2012=p1p2 a_{2012} = p_1 \cdot p_2

### Verification

1. Pairwise GCD Greater than 1:

For any two distinct elements ai=pip2012 a_i = p_i \cdot p_{2012} and aj=pjp2012 a_j = p_j \cdot p_{2012} where i,j<2012 i, j < 2012 , we have:
GCD(ai,aj)=GCD(pip2012,pjp2012)=p2012 \text{GCD}(a_i, a_j) = \text{GCD}(p_i \cdot p_{2012}, p_j \cdot p_{2012}) = p_{2012}

For any such ai a_i and a2012=p1p2 a_{2012} = p_1 \cdot p_2 , we get:
GCD(ai,a2012)=GCD(pip2012,p1p2) \text{GCD}(a_i, a_{2012}) = \text{GCD}(p_i \cdot p_{2012}, p_1 \cdot p_2)

As long as neither p1 p_1 nor p2 p_2 is used among the first 2011 elements (which it isn't because i1,2 i \neq 1, 2 for i<2012 i < 2012 ), the GCD will include at least one factor from the product, hence:
GCD(ai,a2012)=1 \text{GCD}(a_i, a_{2012}) = 1

2. Triple GCD Equal to 1:

Considering any three distinct elements ai a_i , aj a_j , and ak a_k , where two of them are from the first 2011 elements and one is a2012 a_{2012} :
GCD(ai,aj,a2012)=GCD(pip2012,pjp2012,p1p2)=1 \text{GCD}(a_i, a_j, a_{2012}) = \text{GCD}(p_i \cdot p_{2012}, p_j \cdot p_{2012}, p_1 \cdot p_2) = 1

Since the ai a_i are pairwise coprime with the additional element a2012 a_{2012} , the GCD condition with three distinct elements holds, as their triples always share only one prime, thus:
GCD(ai,aj,ak)=1 \text{GCD}(a_i, a_j, a_k) = 1

### Conclusion

By this choice and verification, it demonstrates that such a set S S of 2012 elements satisfying all required conditions can be constructed. Therefore, it is indeed possible to have a set S S with 2012 elements following these conditions. Hence, the answer is:
Yes \boxed{\text{Yes}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.