# Proving that a composite number $n$ has a factor $k \leq \sqrt{n}$

Prove that a composite number $n$ has a factor $k \leq \sqrt{n}$.

Do we prove by proof by contrapositive?

Prove that a prime number $n$ has no factor $k \leq \sqrt{n}$.

Any tip?

-
The purported "contrapositive" is not really the contrapositive of the original statement. I suggest starting with the original statement. What do you know about a composite number? –  Code-Guru Nov 29 '12 at 21:06

By definition if $n$ is composite then $n=ab$ for some positive $a,b$ both not $0$.

If $a\le \sqrt{n}$ then we are done, otherwise $a > \sqrt{n}$ so $b = \frac{n}{a} < \frac{n}{\sqrt{n}} = \sqrt{n}$.

-
If $n$ is composite, then $n=ab$ for some integers $a,b>1$. If $a,b > \sqrt{n}$, then $n=ab>\sqrt{n}\sqrt{n}=n$, a contradiction.