Let $a_1< \cdots< a_n\leq x$, where no $a_i$ divides product of others, show that $n\leq \pi(x)$.

Question

Let $a_1< a_2< \cdots< a_n\leq x$ be a set of positive integers such that no $a_i$ divides the product of the others. Prove that $n\leq \pi(x)$.

---

I have tried to argue by contradiction, which I assume $n> \pi(x)$, then $a_1, a_2, \cdots,a_n$ cannot be mutually relatively prime, so some of $a_i$ must divides product of other $a$'s, but I cannot give a very accurate explanation about it. Any suggestion?

Answer 1

Since no $a_i$ divides the product of the others, then for each fixed index $i$ there must be some prime $p_i$ such that $i\neq j\implies v_{p_i}(a_i)>v_{p_i}(a_j)$. There may, of course, be several such primes...if so, let $p_i$ denote the least of them. Clearly $i\neq j\implies p_i\neq p_j$. In this way we have produced $n$ distinct primes, all less than $x$ so we are done.

Note: here, as usual, for a prime $p$ and a natural number $a$ we define $v_p(a)$ to be the order to which $p$ divides $a$. Thus, for example, $v_3(18)=2$ and $v_5(18)=0$.

Answer 2

Assume to the contrary that there exists $x$ and $a_1<a_2<...<a_n\leq x$ and no $a_i$ divides the product of the others and $n>\pi(x)$. We pick such $a_1,a_2,...,a_n$ and $x$ such that the sum $a_1+a_2+...+a_n$ is minimum. Then we can show that $a_{i}$'s are pairwise coprime.(Suppose that $(a_i,a_j)=d\neq 1$ Then replace (a_i,a_j) by (a_i/d,a_j/d) and consider the minimality of the sum $a_1+a_2+...+a_n$.) Then each $a_i$ has a prime divisor(as $a_i\neq 1$) which does not divide any other $a_j$'s. Therefore each $a_i$ has a distinct prime divisor. Hence there exists at least $n$ primes that are less than or equal to $x$. This is a contradiction. Hence the conclusion follows.