# 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? – Alexey Burdin May 15 '15 at 19:53
• Is there a typo in (d)? I don't understand the difference between (c) and (d). – zuggg May 15 '15 at 20:01
• @AndréNicolas Can you please give input here? – sandy May 15 '15 at 21:27

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