# $X$ is an infinite subset of $\mathbb Z^{+}$ and $T=\{x+y\mid x,y \in X, x\neq y\}$. Prove the set of prime factors of numbers in $T$ is also infinite

Let $$X$$ be an infinite subset of positive integers and $$T=\{x+y\mid x,y \in X, x\neq y\}$$. Prove the set of prime factors of numbers in $$T$$ is also infinite.

My thought was to borrow the idea from the proof that there are infinitely many prime numbers. Suppose the prime factors of $$T$$ is $$\{p_1, p_2,\dots, p_z\}$$ and let $$x=p_1^{n_1} \cdot p_2^{n_2}\cdot \dots \cdot p_z^{n_z}$$ and $$y=p_1^{m_1} \cdot p_2^{m_2}\cdot \dots \cdot p_z^{m_z}$$, prove that we can introduce a new prime factor when we sum $$x+y$$. But unfortunately I didn't get very far. I think I couldn't find a way to leverage the fact that $$X$$ is infinite.

• It is wrong to say that x can be fctorized in such a way only, as it possible that $p_{z+1}$ divides x but it does not divide x+y. Commented Jan 19, 2020 at 4:32

Sorry for deferring the problem to such a deep result such as Thue’s Theorem, but if you don’t mind about that, this does the trick.

Suppose otherwise that every integer in $$T$$ has prime factors of at most $$p$$. Take $$x_1,x_2\in X$$, with $$x_1. It can be proved that there are finitely many $$p$$-smooth numbers at distance $$x_2-x_1$$, see here. Therefore, there can only be finitely many $$x\in\mathbb Z$$ with $$x+x_1,x+x_2\in T$$, contradiction since $$X$$ is infinite. $$\blacksquare$$

An elementary solution

Consider a counterexample to the required result with $$P$$, the set of prime factors of $$T$$, having minimal cardinality.

Lemma 1 Let $$p\in P$$ be odd. Then, for any natural number $$n$$, there are infinitely many elements of $$X$$ which are divisible by $$p^n$$.

Suppose that, for some $$n$$, only finitely many elements of $$X$$ are divisible by $$p^n$$. Then for some $$i$$ there are infinitely many elements of $$X$$ divisible by $$p^i$$ but not $$p^{i+1}$$. Restrict $$X$$ to these elements and then, by dividing every element of $$X$$ by $$p^i$$, we obtain a set where no element of $$X$$ is divisible by $$p$$.

There are only finitely many residue classes modulo $$p$$ and so at least one of these has infinitely many elements in $$X$$. Restrict $$X$$ to this class and let $$x,y\in X$$. Then $$x+y\equiv 2x$$ (mod $$p$$). Then $$p$$ can be dropped from $$P$$ and, by induction, we are finished.

Lemma 2 For any natural number $$n$$, either infinitely many elements of $$X$$ are divisible by $$2^n$$ or all elements are odd and congruent modulo $$4$$ .

As in Lemma 1, we can obtain a set where all elements are odd. Then infinitely many elements are congruent to at least one of $$1$$ and $$3$$ modulo $$4$$. Restrict $$X$$ to an infinite set of congruent elements.

Main proof

Let $$x$$ be any element of $$X$$. For odd $$p\in P$$ let $$p^n$$ be the highest power dividing $$x$$. Delete from $$X$$ all elements other than $$x$$ which are not divisible by $$p^{n+1}$$ and note that this still leaves an infinite set. We can now divide all elements by $$p^n$$. Repeat for all such primes $$p$$.

We are left with an element $$x$$ not divisible by any odd prime in $$P$$ and all other elements in $$X$$ divisible by every odd prime in $$P$$. Furthermore, the same is true for the prime $$2$$ unless all the elements are odd and congruent modulo $$4$$.

Now consider $$x+y$$ for all $$y\in X-x$$. These sums are either not divisible by any prime in $$P$$ or are powers of $$2$$ which are not divisible by $$4$$. This contradiction completes the proof.

• With your Lemma $1$, consider for some odd prime $p$ that $X$ has $2$ elements each with one factor of $p$, and the rest of the elements are all $\equiv 1 \pmod p$. Then $T$ has one element with a factor of $p$, so $p \in P$. However, as stated before, only two elements of $X$ have just one factor of $p$ each, so Lemma $1$ doesn't hold in this case. I think the problem with your proof for this lemma is the base case, i.e., for $n = 1$, as then "for some $i$ there are infinitely many elements of $X$ divisible by $p^i$ but not $p^{I+1}$ is just saying that infinitely many are divisible by $1$. Commented Jan 21, 2020 at 19:36
• @John Omielan. Lemma 1 itself deals with the case you mention. I have rephrased the opening statement to make it more obvious that we are looking at a minimal counterexample.
– user502266
Commented Jan 24, 2020 at 8:42
• Your change now has the statement that $P$ is a set having "minimal" cardinality. However, you don't explain what you mean by "minimal" before starting your Lemma $1$. Also, it seems you're using the set $X$, which is some fixed set in the question, as a changeable set which you are reducing, including in the proof of Lemma $1$ to get the result you want for the statement but only after you run through the proof. A lemma statement should be able to stand on it's own, with the proof to only justify what it says, not create it implicitly. This is the basis of my earlier issue of my comment. ... Commented Jan 24, 2020 at 18:22
• (cont.) I've read through your proof a couple of times, and although I believe I have a general idea of what you're trying to do, I'm not quite clear on how you're trying to do that or how correct your method is. However, I'm not interested in spending any more time & effort on this now. If you're looking for confirmation your proof is correct, perhaps somebody else can do that for you instead, including helping you to improve anything which is unclear or incorrect. Commented Jan 24, 2020 at 18:24
• Minimal cardinality does not need explaining. If a subset of $X$ has infinitely many elements with a particular property then it is obvious that $X$ also has that property. Therefore Lemma 1 does stand on its own. It proves a result about any minimal counterexample to the conjecture.
– user502266
Commented Jan 24, 2020 at 23:09