Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
