Determine all positive integers $n$ for which there exists an infinite subset $A$ of the set $\mathbb{N}$ of positive integers such that for all pairwise distinct $a_1,\ldots , a_n \in A$ the numbers $a_1+\ldots +a_n$ and $a_1a_2\ldots a_n$ are coprime.
Problem
Source: Baltic Way 2010
Tags: induction, number theory proposed, number theory
Rust
19.11.2010 22:50
\[a_i=1+2^{2^i}\] work.
mavropnevma
19.11.2010 23:02
Not quite. But $a_i = p^{i-1}$.
Rust
19.11.2010 23:12
mavropnevma wrote: Not quite. But $a_i = p^{i-1}$. If $A=\{1,p,p^2,...$ $p$ and $p^2$ are distinct elements of A, but $(p+p^2,p*p^2)=p$. Therefore for any prime $p$ only one of $p|a_i$ (not more one) or $(a_i,a_j)=1,i\not =j$. Because if we have infinite sequence, we can chose $a_2,...,a_k$, were $a_1|a_2+...+a_k$ and $a_1|(a_1+a_2+...+a_k,a_1...a_k)$ - contradition.
mavropnevma
19.11.2010 23:18
True; in the whirl of all those bad examples I started to think the set $A$ is ordered $a_1,a_2,\ldots, a_n,\ldots$.
littletush
22.10.2011 14:33
by Dirichlet n=2,trivial for $n\ge 3$ let $a_1$ be a prime greater than n we define by induction when $a_1,...,a_n$ are defined,let $a_{n+1}=ka_1a_2...a_n+1$ be a prime and sufficiently large.