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.

  • $\begingroup$ $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)$. $\endgroup$ – Daniel Fischer Nov 11 '17 at 22:19
  • $\begingroup$ 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. $\endgroup$ – Arin Chaudhuri Nov 11 '17 at 22:28
  • $\begingroup$ 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$. $\endgroup$ – 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$.


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.