# Prove $\pi(x) \geq k$

This is the problem 12 in section 2.2 from LeVeque's Fundamentals of number theory.

If $1 < a_1 < a_2 < \dots < a_k \leq x$ and no $a_i$ divides the product of the rest then prove $\pi(x) \geq k$ (where $\pi(x)$ denotes the number of primes less than or equal to $x$).

The hint is to associate a unique prime to each $a_i$.

The case $k=1$ is trivial so assume $k > 1$ from now on.

I tried to show that there is a prime $p_i$ such that $p_i\mid a_i$ and $p_i\nmid a_j$ for all $j \neq i$, i.e., $p_i \mid a_i$ and $p_i \nmid \prod_{j\neq i} a_j$ for all $i$, but I could not find an argument that worked for all $k$.

However I did observe that if one proves the result for the case where $\operatorname{gcd}(a_1,a_2,\dots,a_k) = 1$ then it is sufficient.

For if $\operatorname{gcd}(a_1,a_2,\dots,a_k) = d > 1$, then we cannot have $a_1=d$ since that violates $a_1 \nmid a_2 \dots a_n$. So we must have $1 < b_1 < b_2 < \dots b_k < x$ where $b_i = \dfrac{a_i}{d}$. We have $\operatorname{gcd}(b_1,\dots,b_k)=1$ and we also have $\dfrac{\prod_{j\neq i} b_j}{b_i} = \dfrac{1}{d^{k-2}}\dfrac{\prod_{j\neq i} a_j}{a_i}$ is not an integer since $\dfrac{\prod_{j\neq i} a_j}{a_i}$ is not.

• $a_i \nmid \prod_{j\neq i} a_j$ means there is a prime $p$ with $v_p(a_i) > \sum_{j \neq i} v_p(a_j)$. – Daniel Fischer Nov 11 '17 at 22:19
• Yes. Is that sufficient to show, there is a prime with $v_p(a_i) > 0$ and $v_p(a_j) = 0$ for $j \neq i$? I am probably missing something obvious. – Arin Chaudhuri Nov 11 '17 at 22:28
• No, it isn't. $a_1 = 12,\, a_2 = 45,\, a_3 = 50$ satisfies the conditions, but every prime dividing one of the three divides two. But it is sufficient to find an injective map from $\{a_1,\dotsc,a_k\}$ to the set of primes $\leqslant x$. – Daniel Fischer Nov 11 '17 at 22:35

We cannot always find a prime $p_i$ dividing $a_i$ but none of the other $a_j$. For example with $k = 3$, $a_1 = 12$, $a_2 = 45$, and $a_3 = 50$, none of the $a_i$ divides the product of the other two, each of $2,3$, and $5$ divides exactly two of the $a_i$, and no other prime divides any of the three.
But we can associate distinct primes to the $a_i$. The condition
$$a_i \nmid \prod_{j \neq i} a_j$$
means there is a prime $p$ such that
$$v_p(a_i) > \sum_{j \neq i} v_p(a_j).$$
If we let $p_i$ any such prime, then $p_i \leqslant a_i \leqslant x$, and for $i \neq j$ we have $p_i \neq p_j$. Thus $\pi(x) \geqslant k$.