A sketch: We will try construct our set $B$ by induction. To do so, for a fixed subset sum of $B$ we will find an infinite set of elements such that each of them added to the sum will have a prime factor not in $P$. Then from this infinite set, we repeat it for another different subset sum of $B$ and if it works for all of them, we can safely add an element into $B$ and continue on. So if we can keep doing this, then we will end up with $B$ being infinite so at some point only finitely many elements can work. So say it fails for some sum $k$. Let $a_1,a_2,\ldots$ be the infinite set of elements that fail for that sum. So we must have $k + a_i$ have all prime factors in $P$. So there must exist an infinite subsequence $b_1,b_2,\ldots$ and a $p_1 \in P$ such that $v_{p_1}(k + b_i) < v_{p_1}(k + b_{i+1})$ because there are only finitely many prime factors. Relabel our $a_i$ with $a_{b_i}$ and now choose a very fast growing sequence $c_1,c_2,\ldots$ and then relabel $a_i$ with $a_{c_i}$. The thing is that now our $a_i$ is of the form $d_i - k$ where $v_p(d_i)$ grows very fast with $i$. So for some sum $a_{k_1} + a_{k_2} + \cdots + a_{k_n} = d_{k_1} + d_{k_2} + \cdots + d_{k_n} - nk$, if $c_i$ increases fast enough say if $p_1^{c_i} > \sum_{k=1}^{i-1} d_k$, then taking mod $p_1^{c_{n-1}}$ we will have the expression is $d_{k_1} + d_{k_2} + \cdots + d_{k_n} - nk \pmod {p_1^{c_{n-1}}}$ which is clearly non-zero if we make $d_{i+1} > d_i + k$. Hence $v_{p_1}$ of the expression is bounded by that of $d_{k_{n-1}}$. Now lets repeat our construction algorithm for the new sequence $a_1,a_2,\ldots$. Similarly it must fail at some sum $m$. Repeat the argument in the above paragraph. Now since $v_{p_1}$ for each sum of $a_i$'s can be bounded such that at most $\frac{1}{c}$ of the sum comes from $p_1$ for any fixed constant $c$ by simply making $c_i$ increase as fast as we want, for our infinite subsequence whose $v_p$ is strictly increasing, we can choose this prime say $p_2 \in P$ to be distinct from $p_1$. Now repeat the argument on $p_2$ to get an infinite sequence $s_1,s_2,\ldots$ such that for any sum at most some small fraction comes from $p_1$ and $p_2$. Hence if our construction algorithm fails on this new sequence, there must be a new prime $p_3 \in P$ where $v_{p_3}$ of some subsequence goes to infinity and so on. However, $P$ is finite so at some point our construction algorithm must work and we are done since each time we fail, we can find a new element of $P$.

A somewhat different approach: suppose $P$ consist of $m$ primes, and let $n = 2^m+1$. We consider a family of subsets $B_1^{t}, B_2^{t}, \dots, B_n^{t}$ of $A$, indexed by a time variable $t$. At time $t = 0$, put one distinct element of $A$ into each $B_i$. At times $t \geq 1$, we will add one element of $A$ into one of the B_k, so that the following two conditions are satisfied: 1) each (nonempty) subset sum of each $B_i$ has a prime factor not in $P$, and 2) the subset sums of $B_i$ are distinct from those of $B_j$. Let us show this is always possible. If adding $x \in A$ fails condition 1), we know there exist subset sums $s_i$ of $B_i^{t-1}$ such that $x + s_i$ only has prime factors in $P$, $\forall 1\leq i \leq n$. By the assumption on $A$, the $s_i$ are non-zero. Therefore by condition 2), they are distinct. We claim there are only finitely many such $x$. Because each $s_i$ has finitely many choices, it suffices to prove the claim for a fixed set of $\{s_i\}_{1\leq i \leq n}$. Moreover, by Pigeonhole principle, there exist $i \neq j$ such that $x+s_i$ and $x+s_j$ have the same square-free part $d | \Pi_{p \in P} p$. Thus the number of such $x$ is bounded above by the number of solutions to $du^2 - dv^2 = s_j - s_i$, where $d, i, j$ each has finitely many choices. Since $s_i \neq s_j$, such an equation does indeed have finitely many solutions, proving our claim. We can thus add some $x \in A$ to one of the $B_i^{t-1}$ to still satisfy condition 1). By choosing $x$ sufficiently large, we can also ensure the second condition. The construction of the subsets $\{B_i^{t}\}_{1\leq i \leq n}$ thus goes on till infinity. To complete the proof, just notice that $\cup_{t} B_i^{t}$ satisfies condition 1) for each $i$, and for some $i$ this union set is infinite.

Dear angiland, I was just wondering, what is the motivation for your beautiful proof, in particular the consideration of the family of subsets $B_1^{t}, B_2^{t}, \dots, B_n^{t}$ of $A$ and the satisfaction of the two conditions (1) each (nonempty) subset sum of each $B_i$ has a prime factor not in $P$, and 2) the subset sums of $B_i$ are distinct from those of $B_j$)? Thank you so much for all your help!

A slightly different from @fattypiggy123: First, we exclude all elements of $A$ that is not greater than $\prod_{p\in P}{p^2}$ from $A$. As usual, we try to inductively construct $B$. For inductive step, we want to use the following procedure to choose the next element. Procedure wrote: For any positive integer $s> \prod_{p\in P}{p^2}$ and infinite list of elements in $A$, called $a_1,a_2,...$: there exists infinitely many $a_i$s that $a_i+s$ has a prime factor not in $P$. For clarity, suppose we already have elements $e_1,e_2,...,e_t$ and want to select $e_{t+1}$. We repeatedly use the proposition when $s$ be sum of finite subsets of $\{ e_1,e_2,...,e_t\}$ with infinite list obtained from the previous use. After we've verified for all possible such $s$, we'll get infinite list of possible $e_{t+1}$, choose one and leave the rest for the next inductive step. If this procedure never fails, we are done. So, suppose it fails when we use it with positive integer $s$ and infinite list $a_1,a_2,...$. We get that for every positive integer $i$, $a_i+s$ must be product of primes from $P$. Our goal is to show that there exists infinite subsequence $a_{i_1},a_{i_2},...$ of the list that can be $B$. Again, we'll inductively construct such subsequence. We'll add a further constraint that all terms in the subsequence are greater than $2s$. Base case: By Thue's theorem, there exists only finitely many non-negative integer solutions $x_p,y_p$ where $p\in P$ to the equation $$\prod_{p\in P}{p^{x_p}}+s=\prod_{p\in P}{p^{y_p}}.$$Hence, there exists infinitely many possible $a_i$s that $a_i$ is not product of primes from $P$. Choose one that is greater than $2s$ and leave the rest of the possible choices for next inductive step. Inductive step: Again, we'll use the same procedure to choose the next element. Let's show that the procedure won't fail. Suppose we've positive integer $r$ and infinite list of elements $b_1,b_2,...$. Recall that all number $b_i$s in our list satisfy $b_i+s$ is product of primes in $P$. And also, the number $r$ we'll use in the procedure also satisfy $r>2s$. If this procedure fails, we get that $b_i+r$ must be product of primes from $P$ for all positive integer $i$. This means we get infinite non-negative integer solutions $x_p,y_p$ where $p\in P$ to the equation $$\prod_{p\in P}{p^{x_p}} -s+r=\prod_{p\in P}{p^{y_p}}.$$This contradict Thue's theorem. And so, we have infinite choice for next element, choose one and leave the rest for the next inductive step, done.

Really elegant problem. China seems to have many great Number Theory problems. Here is my solution, call a positive integer $n$ smooth if and only if all prime factors are in $P$ and rough otherwise. We first prove the following lemma. Lemma : For any constant $c$, there exists finitely many pairs $(x,y)$ of smooth integers such that $x-y=c$. Proof : Write $x = ar^3, y= bs^3$ where $a,b$ is factor of $\prod_{p\in P} p^2$. Clearly we have finitely many pairs $(a,b)$. But by Thue's theorem, equation $ar^3-bs^3=c$ has finitely many solutions $(r,s)$ so we are done. Back to the main problem Define sets $A_1, A_2,...$ as $A_k = \{x\in A\mid x+k\text{ is smooth}\}.$ We split into the two cases. Case 1 : Each of $A_1, A_2, ...$ is a finite set. We proceed with induction. Start with any element of $A$ and keep adding element into $B$. Suppose that currently, $B = \{b_1,b_2,...,b_k\}$. Let $t = b_1+b_2+...+b_k$. Pick element $$b \in A \setminus \bigcup_{i=1}^t A_i$$, which clearly have infinitely many choices. So $b, b+1, b+2,....,b+T$ are all rough. It's easy to see that $B\cup\{b\}$ works. The process continues indefinitely so we are done. Case 2: $A_k$ is infinite for some $k$. Let $T=A_k$, removing every elements less than or equal to $k$. Define $T_1, T_2,...$ as $$T_l = \{t\in T\mid t+l\text{ is smooth}\}.$$By our lemma, $T_l$ is finite as for each element $t$, $t+k$ and $t+l$ is smooth. Now we can induct as before. Start with any element in $T$ and keep adding element into $B$. Suppose that currently, $B=\{b_1, b_2,...,b_l\}$. Let $s = b_1+b_2+...+b_k$. Pick element $$b\in T\setminus \bigcup_{i=k+1}^s T_i$$, which clearly have infinitely many choices. So $b+k+1, b+k+2, ..., b+T$ are all rough. Since every element of $B\subseteq T$ is greater than $k$, it's easy to see that $B\cup \{b\}$ works. The process continues indefinitely so we are done.

We inductively construct a set $B$ that satisfies the condition. We first put one element of $A$ in $B.$ Suppose we now have $\{b_{1},b_{2}, b_{3}, \dots b_{n} \}$ in $B.$ If we can't find another integer $a \in A \setminus B$ to put in $B,$ then that means that there exists an integer $k$ where there is a infinite set $S_k$ of integers $a$ in $A$ such that $k+a$ has all prime factors in $P.$ We claim that for any integer $j \ne k,$ there exist only finitely many integers $b$ such that $j+b$ and $k+b$ have all prime factors in $P.$ Indeed, each $j+b$ and $k+b$ corresponds with a solution to $d(p^2) - d(q^2) = |j - k|$ for some $d \mid \prod_{p \in P} p.$ But for each divisor $d$ there are only finitely many solutions to the equation so the number of possible $b$ is bounded. Now we can construct $B$ inductively using the elements of $S_k$ greater than $k.$ Start by choosing an integer in $S_k$ greater than $k.$ Now suppose we have a finite number of elements in $B$ and want to add another. The number of integers that cannot be added to our set is finite from our earlier claim so choosing a sufficiently large element in $S_k$ suffices. This process may continue indefinitely. Otherwise, we can continue our initial method of construction indefinitely. $\square$

buzzychaoz wrote: Let $P$ be a finite set of primes, $A$ an infinite set of positive integers, where every element of $A$ has a prime factor not in $P$. Prove that there exist an infinite subset $B$ of $A$, such that the sum of elements in any finite subset of $B$ has a prime factor not in $P$. The first idea is to use CRT which doesnt work well since we can't choose stuff,and later we try inducting just to find it works!!

Here's a solution given by my friend, Triangle_Center: Let $|P|=n$ and call a finite set $S$ good if the sum of elements in any finite subset of $S$ has a prime factor that is not in $P$. Consider $n+1$ good sets $A_1,A_2,\ldots,A_{n+1}.$ The crux of the problem is that we can always find some $a\in A,$ different from the elements of $A_1\cup\cdots \cup A_{n+1}$ and some index $1\leq i\leq n+1$ such that $A_i\cup \{a\}$ is good. Assume the contrary. It follows that for any $a\in A\setminus(A_1\cup\cdots \cup A_{n+1})$ and each $1\leq i\leq n+1,$ there exists $B_i\subseteq A_i$ with the property that $a+s(B_i)$ only has prime factors of $P.$ Furthermore, define the function \[f:\mathbb{N}\to\mathbb{N}, \ f(n):=\max_{p\text{ prime}}\big(p^{\nu_p(n)}\big).\]For the sake of brevity, let $s_i:=a+s(B_i).$ Look at $f(s_1),f(s_2),\ldots,f(s_{n+1}).$ It follows by the pigeonhole principle that $f(s_x)$ and $f(s_y)$ are powers of the same prime, for some indices $x$ and $y.$ Therefore, since $f(n)$ divides $n$ for all $n,$ we have \[\min\big(f(s_x),f(s_y)\big)\mid |s_x-s_y|=|s(B_x)-s(B_y)|.\]Note that for any $c>0,$ there exists $N_c$ such that $f(n)>c$ for all $n>N_c.$ Let $C$ be the maximum of $|s(B)-s(C)|$ taken over all pairs of subsets $B\subseteq A_i$ and $C\subseteq A_j.$ Finally, observe that if we take $a>N_C$ then \[\min\big(f(s_x),f(s_y)\big)>C>|s(B_x)-s(B_y)|\]so the divisibility relationship cannot hold. Since $A\setminus(A_1\cup\cdots \cup A_{n+1})$ is infinite, we can for sure find an element $a$ greater than $N_C$ and by the above observations, $A_i\cup\{a\}$ is also good, for some index $i.$ Now, by starting with $A_1=A_2=\cdots=A_{n+1}=\emptyset,$ using the above claim, we can keep adding elements from $A$ to some $A_i$ infinitely many times, resulting in us making an infinite good set. This finishes the proof.