1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user19405892 Jul 25 '16 at 23:15
  • $\begingroup$ 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.$ $\endgroup$ – Mitchell Spector Jul 25 '16 at 23:17
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.