# Infinite set of positive integers such that the greatest common divisor of any two distinct numbers in $B$ is $p$

Let $A$ be an infinite set of positive integers such that every $n \in A$ is the product of at most $k$ prime numbers where $k$ is a positive integer. Prove that there are an infinite set $B \subset A$ and a number $p$ such that the greatest common divisor of any two distinct numbers in $B$ is $p$.

I thought about proving this by induction on $k$. If $k = 1$, then $A$ must be an infinite set of distinct primes and so we let $B$ be an infinite set of primes. Thus, we see that $p = 1$. How do we do the inductive step?

Before proving it, let's resolve an ambiguity in the statement of the problem. The statement "$n$ is the product of at most $k$ prime numbers" must be taken to mean "$n$ can be written as the product of at most $k$ prime numbers, not necessarily distinct." (If we took it to mean "$n$ has at most $k$ prime factors", then $A=$ the set of all powers of $2$ would be a counterexample.)

It was pointed out in a comment (apparently now deleted) that the problem asks for a proper subset of $A.$ In fact, it's sufficient to show that for any set $A$ with the given properties, we can find an infinite $B \subseteq A$ such that any two members of $B$ have the same gcd. After all, if there is such a $B,$ then $B$ with its first element removed is a proper subset of $A$ with the required property.

We'll prove the statement by induction on $k,$ as the OP suggests.

For $k=1,$ take $B=A.$

Now assume the statement is true for $k,$ and let $A$ be an infinite set of positive integers such that each $n \in A$ is the product of at most $k+1$ primes.

Case 1: There exists some number $m > 1$ such that infinitely many multiples of $m$ belong to $A.$ Set $A' = \lbrace n \;\vert\; mn \in A \rbrace,$ and observe that $A'$ is infinite and each member of $A'$ is the product of at most $k$ primes. Let $B$ be an infinite set contained in $A'$ such that the gcd of any two distinct members of $B$ is some fixed number $g.$ Then $\lbrace mb \;\vert\; b \in B \rbrace$ is an infinite subset of $A$ such that any two distinct members of $B$ have gcd $mg.$

Case 2: For every $m,$ only finitely many multiples of $m$ belong to $A.$ Define $b_0, b_1, \dots \in A$ by induction, as follows: let $b_n$ be the least member of $A$ that is greater than 1 and that is not a multiple of any prime that divides some $b_k$ for $k<n.$ Then $B = \lbrace b_0, b_1, \dots \rbrace$ is an infinite subset of $A$ such that any two distinct members of $B$ have gcd $1.$

• How do you know an infinite set $B$ contained in $A'$ exists such that the greatest common divisor of any two distinct members of $B$ is some fixed number $g$? – user19405892 Jul 25 '16 at 23:15
• By the induction hypothesis. Every member of $A'$ is the product of at most $k$ primes, and we've assumed the statement is true for $k.$ – Mitchell Spector Jul 25 '16 at 23:17

HINT: If there is a prime $p$ that is a factor of infinitely many members of $A$, let $B=\{n\in A:p\mid n\}$, and apply the induction hypothesis to $\left\{\frac{n}p:n\in B \right\}$.

If there is no such $p$, show that there is an infinite $B\subseteq A$ such that the members of $B$ are pairwise relatively prime.

For each prime $q$, let $A_q$ be the set of members of $A$ divisible by $q$. Each member of $A$ is in at most $k$ of the sets $A_q$.

Case 1: if all $A_q$ are finite, then it's not hard to show that there are infinitely many nonempty and mutually disjoint $A_q$; taking one member of each of them, you have your $B$ with $p=1$.

Case 2: If some $A_q$ is infinite, replace $A$ by $C_q = \{a/q: a \in A_q\}$. This satisfies the same conditions as $A$, but with $k$ replaced by $k-1$. Using induction, there exist an infinite set $B_q \subseteq C_q$ and $p_q$ which is the gcd of any two members of $B_q$. Let $B = \{bq: b \in B_q$ and $p = q p_q$.

If infinitely many elements of $A$ share a prime factor this is easy.

If they don't, you could try to find elements of $A$ such that they share no prime factors with any other elements of $A$. There are infinitely many primes, so it's easy to think of 'nice' $A$ where this could be possible. This should be true for general $A$ because each $n\in A$ is the product of at most $k$ prime numbers and $A$ is infinite. Thus you must have elements that share no prime factors with other elements - otherwise you would either get a finite set, or an infinite subset that shares a prime factors (which isn't true for this case).