Definition 1 For any number $x$, $N_j(x)$ is the number of positive integers less than or equal to $x$ that have all their prime divisors among the set of the first $j$ primes $\{p_1,p_2,\ldots,p_j\}$.

Definition 2 A number is square-free if none of its divisors is a perfect square (except $1$).

  • (a) Show that there are exactly $2^j$ square-free numbers whose only prime divisors are in the set $\{p_1,p_2,\ldots,p_j\}$.

  • (b) Show that, for all positive integers $x$, $N_j (x) ≤ 2^j\times\sqrt{x}$.

  • (c) Show that, for sufficiently large $x$, $N_j(x) < x$. Why does this mean there must be an infinite number of primes?

  • (d) For subsequent results, we need a little bit more. Show that for sufficiently large $x$, $N_j (x) < x $.

What I have thought:

I really don't know what to do for (a),(c),(d). For (b), can't we show that every positive integer can be written uniquely as the product of a perfect square and a square-free number?

  • $\begingroup$ (a) These numbers are in form $p_1^{\alpha_2}p_1^{\alpha_2}\cdot\dots\cdot p_j^{\alpha_j}$ where $\alpha_k \in \{0,1\}$. Btw, does (c) and (d) differ? $\endgroup$ May 15, 2015 at 19:53
  • $\begingroup$ Is there a typo in (d)? I don't understand the difference between (c) and (d). $\endgroup$
    – zuggg
    May 15, 2015 at 20:01

1 Answer 1


(a): Let $A_j$ be the set of these numbers. Then $A_j$ is in bijection with the power set of $\{p_1,p_2,\ldots,p_j\}$ per $n\mapsto\{\,p\text{ prime}:p\mid n\,\}$

(b): Let $B_j(x)$ be the set of these numbers. Writing a number $n\in B_j(x)$ as $n=ab^2$ with $a$ square-free, we obtain an injection $B_j(x)\to A_j\times\{1,\ldots,\lfloor \sqrt x\rfloor\}$, $n\mapsto (a,b)$.

(c): For fixed $j$, we can consider $x>2^{2j}$ and find from (b) that $N_j(x)<2^j\cdot \sqrt{x}<\sqrt x\sqrt x = x$. If there are only finitely many primes, we can let $j$ be the number of priems and yet find that there are numbers in $\{1,\ldots,2^{2j}\}\setminus S_j(2^{2j})$, contradiction.

(d) is the same as c.

  • $\begingroup$ What does the \ mean in {1,…,22j}∖Sj(22j), $\endgroup$
    – sandy
    May 15, 2015 at 20:14
  • $\begingroup$ Could you provide a more elementary approach to these parts if you can? $\endgroup$
    – sandy
    May 15, 2015 at 20:15

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.