# integer n as a product of primes, 2, 3,…P, P is less than or equal to $\sqrt{n}$

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?

• What is $n{{}}$? – Lord Shark the Unknown Nov 9 '18 at 7:40
• hi. n is integer. – zono Nov 9 '18 at 7:43
• You are not excluding $n$ prime? – Lord Shark the Unknown Nov 9 '18 at 7:47
• 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? – fleablood Nov 9 '18 at 7:50
• "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. – zono Nov 9 '18 at 8:08

## 3 Answers

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

• 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. – fleablood Nov 9 '18 at 8:20
• @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. – YiFan Nov 9 '18 at 8:27
• 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. – fleablood Nov 9 '18 at 8:29
• I'm sorry for my vague question. I'm trying to understand your comments and answers now. – 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. 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$$.