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!

  • 1
    $\begingroup$ Are $p_1, p_2,\dots,p_k$ all the primes less than or equal to $N$? $\endgroup$
    – paw88789
    Sep 23, 2014 at 10:51
  • 1
    $\begingroup$ @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$. $\endgroup$ Sep 23, 2014 at 11:33

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$ Sep 24, 2014 at 9:17
  • $\begingroup$ @Jean-ClaudeArbaut I see, I've proved that there are infinitely many primes with the idea of exercise. Ok, I could change something to make the proof match both the questions. $\endgroup$ Sep 24, 2014 at 14:00
  • $\begingroup$ That's perfect! It is clear and easily understood. $\endgroup$ Sep 25, 2014 at 9:50
  • $\begingroup$ @ThomasYang I guess you want to close the question then. $\endgroup$ Sep 25, 2014 at 9:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .