# Why any integer $n$ can only have one prime factor greater than $\sqrt{n}$?

I know the proof that for a composite number $$n$$, there is at least one prime factor less than or equal to $$\sqrt{n}$$ but I don't know how to prove this following statement:

Any number $$n$$ can have only one prime factor greater than $$\sqrt{n}$$.

So is there a connection between these two statements? How do you prove the second statement?

• If there are two, what about their product? May 27, 2020 at 19:32

Assume the contrary: $$n=p_1p_2r$$ where $$p_1,p_2>\sqrt{n}$$, and $$r$$ contains all other factors in $$n$$. Then let $$t=p_1p_2>\sqrt{n}\cdot \sqrt{n}=n$$
Then $$n=tr>n$$. This is a contradiction, so the assumption must be false.
Assume that $$n$$ can be decomposed as $$n = a_1^{b_1}a_2^{b_2}\dots a_k^{b_k}$$ where $$a_i, \quad i=\left\{1,2,\dots,k\right\}$$ are prime numbers and $$b_i\geq 1\in \mathbb{Z}$$. Assume that you are investigating if $$n$$ is prime or not. You divide $$n$$ by $$d =2,3,4....$$ respectively. So if any $$d==a_i$$, you stop the iteration and decide that $$n$$ is not a prime number. In another saying, we now convert our problem into an optimization problem such that $$\max d$$ $$\textit{subj. to }\quad n = a_1^{b_1}a_2^{b_2}\dots a_k^{b_k}$$ So it is equivalent to $$\max a_i$$ $$\textit{subj. to }\quad n = a_1^{b_1}a_2^{b_2}\dots a_k^{b_k}$$ as it is seen form the optimization problem, the best way is setting $$a_j =1, i\neq j$$ then $$n = a_i^{b_i}$$ and in order to maximize $$a_i$$ you can either select $$b_i=1$$, which equalizes $$n=a_i$$. The second option as you mentioned is to take the $$b_i=2$$ resulting in $$a_i= \sqrt{n}$$ which concludes the proof.Briefly, $$n = \sqrt{n}$$ is obtained.