Olympiad Maths Prep

Track / Stage 6 / 299 of 400 #1299 of 2000

Problem 1299

National olympiad, first round
Number theory Difficulty 6.5 Find the answer

Find all positive integers nn such that there exists an infinite set AA of positive integers with the following property: For all pairwise distinct numbers a1,a2,,anAa_1, a_2, \ldots , a_n \in A, the numbers
a1+a2++an and a1a2ana_1 + a_2 + \ldots + a_n \text{ and } a_1\cdot a_2\cdot \ldots\cdot a_n
are coprime.

Official solution

1. **Case for n=1 n = 1 :**
- If n=1 n = 1 , we need to find a set A A such that for any a1A a_1 \in A , the number a1 a_1 is coprime with itself. This is impossible because any number is not coprime with itself. Hence, there is no such set A A for n=1 n = 1 .

2. **Case for n2 n \geq 2 :**
- We need to construct an infinite set A A of positive integers such that for any n n pairwise distinct numbers a1,a2,,anA a_1, a_2, \ldots, a_n \in A , the sum a1+a2++an a_1 + a_2 + \ldots + a_n and the product a1a2an a_1 \cdot a_2 \cdot \ldots \cdot a_n are coprime.

3. Choosing primes:
- Let p1 p_1 be a prime number greater than n n .
- For i2 i \geq 2 , choose pi p_i such that:
pi1(modp1p2pi1)andpi>p1+p2++pi1+n p_i \equiv 1 \pmod{p_1 \cdot p_2 \cdots p_{i-1}} \quad \text{and} \quad p_i > p_1 + p_2 + \cdots + p_{i-1} + n
By Dirichlet's theorem on arithmetic progressions, such primes pi p_i exist.

4. **Constructing the set A A :**
- Let A={p1,p2,p3,} A = \{ p_1, p_2, p_3, \ldots \} .

5. Verifying the coprimality condition:
- Consider any n n pairwise distinct numbers q1,q2,,qnA q_1, q_2, \ldots, q_n \in A with q1<q2<<qn q_1 < q_2 < \cdots < q_n .
- Assume there exists a prime r r such that r r divides both q1+q2++qn q_1 + q_2 + \cdots + q_n and q1q2qn q_1 \cdot q_2 \cdot \cdots \cdot q_n .
- Since r r divides q1q2qn q_1 \cdot q_2 \cdot \cdots \cdot q_n , r r must be one of the qi q_i , say r=qt r = q_t for some t{1,2,,n} t \in \{1, 2, \ldots, n\} .

6. Deriving a contradiction:
- Since qt q_t divides q1+q2++qn q_1 + q_2 + \cdots + q_n , we have:
qtq1+q2++qt1+qt+1++qn q_t \mid q_1 + q_2 + \cdots + q_{t-1} + q_{t+1} + \cdots + q_n
- Given the construction of pi p_i , we have qt+1qt+2qn1(modqt) q_{t+1} \equiv q_{t+2} \equiv \cdots \equiv q_n \equiv 1 \pmod{q_t} .
- Therefore, qtq1+q2++qt1+(nt) q_t \mid q_1 + q_2 + \cdots + q_{t-1} + (n - t) .

7. **Bounding qt q_t :**
- Let Qt={xA:x<qt} Q_t = \{ x \in A : x < q_t \} . Clearly, q1,q2,,qt1Qt q_1, q_2, \ldots, q_{t-1} \in Q_t .
- By construction, qt>(sum of the elements of Qt)+nq1+q2++qt1+n q_t > (\text{sum of the elements of } Q_t) + n \geq q_1 + q_2 + \cdots + q_{t-1} + n .
- This implies qt>q1+q2++qt1+(nt) q_t > q_1 + q_2 + \cdots + q_{t-1} + (n - t) , which contradicts the earlier condition that qtq1+q2++qt1+(nt) q_t \mid q_1 + q_2 + \cdots + q_{t-1} + (n - t) .

8. Conclusion:
- The contradiction implies that no such prime r r exists, and thus q1+q2++qn q_1 + q_2 + \cdots + q_n and q1q2qn q_1 \cdot q_2 \cdot \cdots \cdot q_n are coprime.

The final answer is all positive integers except n=1 \boxed{ n = 1 } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.