0
$\begingroup$

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?

$\endgroup$
1
  • 11
    $\begingroup$ If there are two, what about their product? $\endgroup$ May 27, 2020 at 19:32

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.