I have no idea how should I start to answer this question.

Show that to write integer n as a product of primes, 2, 3,...P, P is less than or equal to $\sqrt{n}$.

Can you give me a clue to show it?

  • $\begingroup$ What is $n{{}}$? $\endgroup$ – Lord Shark the Unknown Nov 9 '18 at 7:40
  • $\begingroup$ hi. n is integer. $\endgroup$ – zono Nov 9 '18 at 7:43
  • $\begingroup$ You are not excluding $n$ prime? $\endgroup$ – Lord Shark the Unknown Nov 9 '18 at 7:47
  • $\begingroup$ So you saying. If the $n$ is the product $p_1p_2.... p_k$ where $p_1, p_2,... p_k$ are the first $k$ primes then $p_k \le \sqrt n$? For instace. $2\le \sqrt 2$ (which is isn't), $3\le \sqrt {2*3}$ (which it isn't), and $5\le \sqrt 2*3*5$. And in still other words that would mean $p_k < p_1p_2 .... p_{k-1}$ if $k > 2$. Is that what you are asking? $\endgroup$ – fleablood Nov 9 '18 at 7:50
  • $\begingroup$ "If the n is the product $p_1p_2...pk$ where $p_1p_2...pk$ are the first $k$ primes then $pk \le \sqrt{n}$" yes exactly. $\endgroup$ – zono Nov 9 '18 at 8:08

Edit: the OP appears to be asking a different question than what I interpreted. I'll leave this answer here to remove any doubts that this (different) claim might be true.

The claim is that any integer $n$ can be expressed as a product of primes each less than or equal to $\sqrt n$. Well, you certainly cannot prove this claim, since it is false. Here are a few examples whose only factorisations do not satisfy the claim. $$\begin{split} 17 & = 17 \quad \text{but }17>\sqrt{17}\\ 23 & = 23 \quad \text{but }23>\sqrt{23}\\ 14 & = 2\times 7\quad \text{but }7=\sqrt{49}>\sqrt{14}\\ 55 & = 5\times 11 \quad \text{but }11=\sqrt{121}>\sqrt{55} \end{split}$$

  • $\begingroup$ I think that that is not the claim at all. I think the claim is that if $n$ is the product of the first several primes. then the last of the primes is less than the square root of $n$. This is not true unless the last prime is $5$ or higher, but otherwise it is true. $\endgroup$ – fleablood Nov 9 '18 at 8:20
  • $\begingroup$ @fleablood I honestly don't know, the phrasing in the problem (at the time I'm writing this) is really vague and this is my best interpretation. $\endgroup$ – YiFan Nov 9 '18 at 8:27
  • $\begingroup$ I agree it is very vaguely written. I asked in the comments what was meant and if the OP understood me s/he confirmed my interpretation. $\endgroup$ – fleablood Nov 9 '18 at 8:29
  • $\begingroup$ I'm sorry for my vague question. I'm trying to understand your comments and answers now. $\endgroup$ – zono Nov 9 '18 at 8:43

This isn't true for $P= 2$ and $2 > \sqrt{2}$ and for $P = 3$ and $3 > \sqrt {2*3}$ but for $P \ge 5$ it is true. For example: $5 < \sqrt {2*3*5}$.

Suppose $p_1, .... ,p_k$ are the first $k$ primes.

Then this is statement is $p_k \le \sqrt {p_1p_2....p_k}$.

This true iff and only if $p_k^2 \le p_1p_2....p_k$ which is true if and only if

$p_k \le p_1p_2....p_{k-1}$.

Which is easy to prove:

I claim that for $k\ge 3$ then $p_{k} < p_1p_2.... p_{k-1}$ (assuming $p_k \ge p_3 = 5$).

Pf: Consider $M=2\cdot 3.... p_{k-1} -1 \ge 2*3 - 1 = 5 > 1$. None of the $p_i; i\le k-1$ divide into $M$. So either some other prime, $p_m$, does. So there exists a $p_{m}\ge p_k > p_{k-1}$ that divides into and is therefore less than or equal to $M= 2\cdot 3.... p_{k-1} -1$.

(Note: we needed the condition $k \ge 3$ to assure that $M = p_1p_2...p_{k-1} -1 > 1$.)

(Also note: the $p_m$ that divides into $M$ doesn't need to be $p_k$. But if it isn't $p_k$ then it must be a prime larger than $p_k$. Example: $M = 2*3*5-1 = 29$ and so $2,3,5$ do not divide $29$ so there is a prime greater than $5$ that divides $29$. That prime is $29$. So the next prime after $5$ (which is $7$) must be $\le 29$. And $7 \le M = 2*3*5 -1$. )

Also note: $p_k$ is strictly less than $\sqrt {p_1...p_k}$ (which is an irrational number anyway....)


Let $q$ be the penultimate of the primes. By Bertrand's postulate, $q<p<2q$. Except for the cases $n=2$ (where $2>\sqrt 2$) and $n=2\cdot 3$ (where $3>\sqrt 6$), the three distinct factors $2$, $q$, $p$ occur in $n=2\cdot\ldots\cdot q\cdot p$, making $n\ge 2\cdot q\cdot p>p^2$, or: $p<\sqrt n$.


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.