# Exercise in number theory

The problem is as follows:

(a) Let $N$ be a natural number. Let $p_1,p_2,...p_k\leq N$ be all prime numbers less than or equal to N. Prove there is a unique factorization for any $n\leq N$ as follows:

$$n=b^2p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$

where $b^2\leq N$, and $e_1,e_2,...,e_k\in\{0,1\}$.

(b) Show that $2^k\geq \sqrt N$. Hence show that there are infinitely many primes.

Part (a) is easy for me but I do not know how to prove the first inequality in part (b). Could anyone help me? Thanks!

• Are $p_1, p_2,\dots,p_k$ all the primes less than or equal to $N$? Commented Sep 23, 2014 at 10:51
• @Ja͢ck The point is to use the (a) to solve (b). The inequality is equivalent to prove that there are at least $\sqrt{N}$ squarefree numbers below $N$. Commented Sep 23, 2014 at 11:33

a) Write $n = \prod_1 ^k p_i ^ {m_i}$ It's the unique factorization theorem. Then write $m_i = 2 k_i + e_i$ Your $e_i$ are clearly defined there and is given by $b = \prod_1 ^k p_i ^ {k_i}$
b) Assume now we have $N$ such that $\sqrt {N} > 2^k$. We have at maximum $2^k$ free of squares numbers (they are not divisible by any square). Let's estimate how many numbers we could give a representation between $1$ and $N$ (including borders). There are $[\sqrt {N}]$ exact squares not greater then $N^2$. So we could represent at maximum $2^k [\sqrt {N}]$ numbers. But we have $2^k [\sqrt {N}] < N$ since $2^k < \sqrt {N}$. And we couldn't represent all the $\{1, ... N\}$. So we should have $\sqrt {N} \le 2^k$ for any $N$, hence we can have arbitrary large $k$.
• For (b), notice $N$ is fixed and the $p_i$ are all the primes below $N$. So "taking a large $R$" in your proof can't work. Commented Sep 24, 2014 at 9:17