# Counting and bounding square-free numbers formed from only the first $j$ primes

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?

• (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? May 15, 2015 at 19:53
• Is there a typo in (d)? I don't understand the difference between (c) and (d). May 15, 2015 at 20:01

(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.