"if $n$ is a composite integer, then $n$ has a prime factor not exceeding ${\sqrt n}$" - proof explanation

Question

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

1. $${\sqrt n} \lt a \le b$$

and as a result,

2. $$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.

Answer 1

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

Answer 2

If $1\lt a \le b \lt n$ and $ \sqrt{n}\lt a$ then

• $ 1 \lt \sqrt{n}$ since both are positive and $1^2 \lt \sqrt{n}^2$
• $ \sqrt{n}\lt a \le b$ and so $ \sqrt{n}\lt b$ by transitivity
• $0 \lt (a-\sqrt{n})\sqrt{n}$ and $0 \lt a(b-\sqrt{n})$ since the real numbers are an ordered field, so $n=\sqrt{n}\sqrt{n} \lt a \sqrt{n} \lt a b$