Show that there exists a set A of positive integers with the following property: for every infinite set S...

arithmetic/prime.products.set New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Show that there exists a set A of positive integers with the following
property: for every infinite set S of primes, there is an integer n in
A and an integer m not in A each of which is the product of k distinct
elements of S, for some k > 1.  [The same k for n and m, else the
problem is trivial.]

[ Editor: a query to the rec.puzzles oracle from jball@max.ma.utexas.edu,
1994. ]

Show solution

There are several solutions to this, but the easiest one is to let the
set A consist of all numbers such that the number of prime factors
equals the smallest prime factor, e.g. 2*2, 2*11, 3*5*101, etc.

For a given infinite set of primes S, let p be the smallest prime in S,
q the 2nd smallest.  Then p*(the p-1 smallest primes in S > p) is in A,
but q*(the p-1 smallest primes > q) is not.

-- Chris Long <clong@cnj.digex.net>