Find all positive integers $n$ such that there exists an infinite set $A$ of positive integers with the following property: For all pairwise distinct numbers $a_1, a_2, \ldots , a_n \in A$, the numbers $$a_1 + a_2 + \ldots + a_n \text{ and } a_1\cdot a_2\cdot \ldots\cdot a_n$$are coprime.
Problem
Source: Swiss IMO TST 2020 P2
Tags: number theory, coprime
BarisKoyuncu
28.09.2021 20:55
Answer: All positive integers except $n=1$. Clearly, for $n=1$, we don't have such set. Let $n\ge 2$. Take a prime greater than $n$, say $p_1$. We will choose $p_i$ for $i=2,3,\cdots$ such that $p_i\equiv 1\pmod{p_1\cdot p_2\cdots p_{i-1}}, p_i>p_1+p_2+\cdots +p_{i-1}+n$ and $p_i$ is prime. By Dirichlet's theorem, we know that such prime numbers exist. Suppose that $A=\{p_1,p_2,\cdots \}$. Let $q_1,q_2,\cdots ,q_n\subset A$. WLOG $q_1<q_2<q_3<\cdots <q_n$. We will prove that the numbers $q_1+q_2+\cdots +q_n$ and $q_1\cdot q_2\cdots q_n$ are coprime. Assume that there exist a prime number $r$ such that $r$ divides $q_1+q_2+\cdots +q_n$ and $q_1\cdot q_2\cdots q_n$. Since $r|q_1\cdot q_2\cdots q_n$, we have $r=q_t$ where $t\in [1,n]$. Then, $q_t|q_1+q_2+\cdots +q_n$. We have $q_{t+1}\equiv q_{t+2}\equiv \cdots \equiv q_n\equiv 1\pmod{q_t}$. So, $q_t|q_1+q_2+\cdots +q_{t-1}+(n-t)$. Let $Q_t=\{x: x\in A, x<q_t\}$. Clearly, $q_1,q_2,\cdots ,q_{t-1}\in Q_t$. Then, $q_t>(\text{sum of the elements of }Q_t)+n\ge q_1+q_2+\cdots +q_{t-1}+n>q_1+q_2+\cdots +q_{t-1}+(n-t)$. Contradiction.
Tintarn
28.09.2021 21:39
It is cute...and it is NT...but it is not from Switzerland! This is an old and classical problem from Baltic Way 2010. See here.