Maths Olympiad Prep

Library / European Mathematical Cup /6 of 26

European Mathematical Cup

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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=pi⋅p2012 a_i = p_i \cdot p_{2012}

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

a2012=p1⋅p2 a_{2012} = p_1 \cdot p_2

### Verification

1. Pairwise GCD Greater than 1:

For any two distinct elements ai=pi⋅p2012 a_i = p_i \cdot p_{2012} and aj=pj⋅p2012 a_j = p_j \cdot p_{2012} where i,j<2012 i, j < 2012 , we have:
GCD(ai,aj)=GCD(pi⋅p2012,pj⋅p2012)=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=p1⋅p2 a_{2012} = p_1 \cdot p_2 , we get:
GCD(ai,a2012)=GCD(pi⋅p2012,p1⋅p2) \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 i≠1,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(pi⋅p2012,pj⋅p2012,p1⋅p2)=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.