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

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.