the proof of this theorem was as follows:
since $n$ is composite, then $n=ab$, where $a$ and $b$ are integers with $1\lt a \le b \lt n$. Suppose now that $a \gt {\sqrt n}$, then
- $${\sqrt n} \lt a \le b$$
and as a result,
- $$ab \gt {\sqrt n}{\sqrt n} = n$$
Therfore, $a \le {\sqrt n}$. Also, $a$ must have a prime divisor $a_1$which is also a prime divisor of $n$ thus this divisor is less than $a_1 \le a \le {\sqrt n}$
What I am having problem with is step 2 I am not sure how this inequality was achieved. I also don't understand the rest of the proof. I would be very grateful if someone could explain it to me.
Best Answer
We know that if $p$ is positive and $q>r$, then $pq>pr$. Using this twice, we get $$ab>a\sqrt n = \sqrt n a > \sqrt n \sqrt n = n $$
First we use the fact with $p=a$, $q=b$ and $r=\sqrt n$.
Then we use it again with $p=\sqrt n$, $q=a$ and $r=\sqrt n$.